У Феникса есть \(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
|
4
1 5
314 15
-99 99
123 987
|
6
329
0
1110
|