Вам дано мультимножество \(S\). Изначально \(S = \{1,2,3, \ldots, n\}\).
Вы выполните следующую операцию \(n-1\) раз.
- Выберите наибольшее число \(S_{\text{max}}\) в \(S\) и наименьшее число \(S_{\text{min}}\) в \(S\). Удалите эти два числа из \(S\) и добавьте \(S_{\text{max}} - S_{\text{min}}\) в \(S\).
Легко показать, что после \(n-1\) операций останется ровно одно число. Выведите это число.
Выходные данные
Для каждого набора входных данных выведите число, которое останется после \(n-1\) операции.
Примечание
Покажем, как изменится мультимножество \(S\) при \(n=4\).
- Операция \(1\): \(S=\{1,2,3,4\}\), удаляем \(4\) и \(1\), добавляем \(3\).
- Операция \(2\): \(S=\{2,3,3\}\), удаляем \(3\) и \(2\), добавляем \(1\).
- Операция \(3\): \(S=\{1,3\}\), удаляем \(3\) и \(1\), добавляем \(2\).
- Получившееся мультимножество: \(S = \{2\}\).
Таким образом, при \(n = 4\) ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
4
7
15
177567
|
1
2
2
4
33914
|