У Кли есть массив \(a\) длиной \(n\), содержащий целые числа \([k, k+1, ..., k+n-1]\) в этом порядке. Кли хочет выбрать индекс \(i\) (\(1 \leq i \leq n\)) так, чтобы \(x = |a_1 + a_2 + \dots + a_i - a_{i+1} - \dots - a_n|\) был минимален. Обратите внимание, что для произвольного целого числа \(z\), \(|z|\) представляет собой модуль числа \(z\).
Выведите минимально возможное значение \(x\).
Выходные данные
Для каждого набора входных данных выведите минимальное значение \(x\).
Примечание
В первом примере \(a = [2, 3]\). При выборе \(i = 1\), \(x = |2-3| = 1\). Можно показать, что это минимально возможное значение \(x\).
В третьем примере \(a = [3, 4, 5, 6, 7]\). При выборе \(i = 3\), \(x = |3 + 4 + 5 - 6 - 7| = 1\). Можно показать, что это минимально возможное значение \(x\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 2
7 2
5 3
1000000000 1000000000
|
1
5
1
347369930
|