Задана последовательность целых чисел \(1, 2, \dots, n\). Вам необходимо разделить ее на два множества \(A\) и \(B\) таким образом, что каждый элемент принадлежит ровно одному множеству, а значение \(|sum(A) - sum(B)|\) — минимально возможное.
Здесь \(|x|\) — абсолютное значение \(x\), а \(sum(S)\) — сумма элементов множества \(S\).
Выходные данные
Выведите одно целое число — минимально возможное значение \(|sum(A) - sum(B)|\), если вы разделите заданную последовательность \(1, 2, \dots, n\) на два множества \(A\) и \(B\).
Примечание
Некоторые (не все) возможные ответы на тестовые примеры:
В первом тестовом примере вы можете разделить заданную последовательность на множества \(A = \{1, 2\}\) and \(B = \{3\}\), таким образом ответ равен \(0\).
Во втором тестовом примере вы можете разделить заданную последовательность на множества \(A = \{1, 3, 4\}\) и \(B = \{2, 5\}\), таким образом ответ равен \(1\).
В третьем тестовом примере вы можете разделить заданную последовательность на множества \(A = \{1, 4, 5\}\) и \(B = \{2, 3, 6\}\), таким образом ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
0
|
|
2
|
5
|
1
|
|
3
|
6
|
1
|