У Феникса есть \(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
|
6
10
2
4
6
7
13
|
9 6 10 8 4 7 3 1 5 2
-1
3 1 4 2
5 3 6 2 4 1
5 1 3 6 2 4 7
13 9 7 11 8 4 1 3 5 2 6 10 12
|