Задача H. В поисках равновесия ≡

Условие

"— Осторожней, — пискнул одноглазый капитан.

Но было уже поздно. Слишком много любителей скопилось на правом борту васюкинского дредноута. Переменив центр тяжести, барка не стала колебаться и в полном соответствии с законами физики перевернулась." (И.Ильф, Е.Петров. "Двенадцать стульев").

После ряда экспериментов, изрядно промокшие шахматные любители поняли, что:

1) количество гребцов в барке должно быть одинаковым по обоим бортам.

2) барка весьма неустойчива, поэтому нужно распределить гребцов таким образом, чтобы вес людей с одной стороны лодки как можно меньше отличался от веса людей с другой стороны.

Несмотря на то, что Ипполит Матвеевич и Остап Ибрагимович давно скрылись из виду, помогите шахматистам определить наименьшую разницу весов на обоих бортах.

Формат входных данных

Первая строка входного файла содержит одно натуральное четное число n - количество людей, бросившихся в погоню. Во второй строке через пробел записаны n натуральных чисел a_i - веса шахматных любителей.

Формат выходных данных

Выведите одно неотрицательное целое число - наименьшую разницу весов. Учтите, что никто из преследователей не хочет остаться на берегу и требует места в барке.

Ограничения

2 ≤ n ≤ 20

1 ≤ a_i ≤ 10⁶

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В первом примере всего два шахматиста. Разница их весов не может быть улучшена.

Во втором примере шестерых людей можно разделить на две группы с равными весами 50 + 50 + 100 и 80 + 60 + 60.

Примеры тестов

2
70 80

10

6
50 80 60 50 100 60

0