Каждое воскресенье Андрей вместе с друзьями играет в футбол. На каждую игру приходит одно и то же (чётное) количество человек. Когда друзья собираются, первым делом они начинают обсуждать, как им разделиться на две команды.
Обычно дискуссии по поводу того, как именно разделиться, занимают очень много времени. Однажды друзьям надоело дискутировать, и они придумали следующий способ. Каждый раз случайным образом выбираются два капитана, после чего капитаны набирают игроков в свои команды.
Чтобы не было новых споров и обид, капитаны по очереди выбирают по одному игроку среди тех, кто ещё не включён в какую-либо команду. Каждый капитан стремится набрать как можно более сильную команду и потому выбирает самого сильного среди ещё не выбранных игроков. Сила игрока — это целое число от 1 до 100 (как в FIFA). Сила команды вычисляется как суммарная сила всех игроков в этой команде, включая капитана.
Андрею стало интересно, какой может быть минимальная разница в силе между командами. Но он очень занят подготовкой контеста по программированию, поэтому просит вас найти эту величину.
На всякий случай ещё раз напомним, что в роли капитанов могут оказаться два любых игрока, не обязательно самые сильные.
В первой строке записано единственное целое число n (2 ≤ n ≤ 400) — количество человек, пришедших на игру. Гарантируется, что n — чётное.
Во второй строке записаны целые числа a1, a2, ..., an, где ai (1 ≤ ai ≤ 100) — сила i-го игрока.
Выведите единственное целое число — минимально возможную разницу в силе команд.
## Входные Данные
В первой строке записано единственное целое число n (2 ≤ n ≤ 400) — количество человек, пришедших на игру. Гарантируется, что n — чётное.Во второй строке записаны целые числа a1, a2, ..., an, где ai (1 ≤ ai ≤ 100) — сила i-го игрока.
## Выходные Данные
Выведите единственное целое число — минимально возможную разницу в силе команд.
## Примеры
Входные данные61 2 3 4 5 6Выходные данные1Входные данные890 93 86 65 78 81 71 86Выходные данные0
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of players, with $ n $ even and $ 2 \leq n \leq 400 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers representing player strengths, where $ 1 \leq a_i \leq 100 $.
**Constraints**
1. $ n $ is even.
2. $ a_i \in \mathbb{Z} $, $ 1 \leq a_i \leq 100 $ for all $ i \in \{1, \dots, n\} $.
**Objective**
Choose two distinct players as captains. The remaining $ n-2 $ players are distributed between the two teams in order of descending strength: at each step, the current captain selects the strongest available player.
Minimize the absolute difference between the total strengths of the two teams over all possible choices of two captains and the resulting greedy selection process.
Formally, for every unordered pair $ \{i, j\} $ with $ i \ne j $, let $ T_1 $ and $ T_2 $ be the teams formed by:
- Sorting $ A \setminus \{a_i, a_j\} $ in descending order: $ b_1 \geq b_2 \geq \dots \geq b_{n-2} $,
- Assigning $ b_1 $ to the team of the captain with higher strength (or arbitrarily if equal), then alternating assignments.
- Adding the two captains to their respective teams.
Compute:
$$
\min_{\substack{i,j \in \{1,\dots,n\} \\ i \ne j}} \left| \text{sum}(T_1) - \text{sum}(T_2) \right|
$$