У Феникса есть \(n\) монет с весами \(2^1, 2^2, \dots, 2^n\). Он знает, что \(n\) — четное.
Он хочет сложить монеты в две кучки так, что в каждой кучке будет ровно \(\frac{n}{2}\) монет и разница суммарных весов между кучками будет минимальна. Формально, обозначим за \(a\) сумму весов в первой кучке, а за \(b\) — сумму весов во второй. Помогите Фениксу минимизировать \(|a-b|\), то есть модуль числа \(a-b\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимально возможную разницу весов между двумя кучками.
Примечание
В первом наборе входных данных, у Феникса есть две монеты с весами \(2\) и \(4\). Как бы он ни разделил монеты, разница будет равна \(4-2=2\).
Во втором наборе входных данных, у Феникса есть четыре монеты с весами \(2\), \(4\), \(8\) и \(16\). Фениксу выгодно положить монеты с весами \(2\) и \(16\) в одну кучку, а монеты с весами \(4\) и \(8\) — в другую. Разница будет равна \((2+16)-(4+8)=6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
11
3 1 4 1 5 9 2 6 5 3 5
1
1000
3
1 1 1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
2
2 1
6
1 1 1 1 1 1
7
1 1 1 1 1 1 1
|
6 23 21
1 1000 0
2 1 2
6 45 46
2 2 1
3 4 2
4 4 3
|