Problem 0E. Erasing numbers ≡

Statement

In the research institute where Timofey works, a successful study of the sequence of natural numbers is underway. Every day, his colleagues discover new and new properties of this sequence, and Timofey tries to keep up with them. Today, as usual, Timofey wrote down a row of natural numbers from 1 to n on the board and tries to answer the question of whether it is possible to erase several (at least one) consecutive numbers in the middle of the list so that the sum of the remaining numbers on the left is equal to the sum of the remaining numbers on the right.

Input format

The input consists of a single line containing a natural number n.

Output format

The output should include a non-negative integer, representing the number of different ways to erase numbers.

Constraints

3 ≤ n ≤ 10⁵

Explanations for examples

In the first example, n = 5. Let's list all the ways to erase numbers in the middle of the row:

• 1 # 3 4 5
• 1 2 # 4 5
• 1 2 3 # 5
• 1 # # 4 5
• 1 2 # # 5
• 1 # # # 5

In none of them does the required property hold.

In the second example, n = 21. Let's list all the good ways to erase numbers in the middle of the row:

• 1 2 3 4 5 6 # # # ## ## ## ## ## ## ## ## ## ## ## 21
• 1 2 3 4 5 6 7 8 9 10 11 12 ## ## ## ## ## 18 19 20 21

In the first list, the sum of the numbers on the left and right is 21, in the second — 78. There are two ways in total.

Sample tests

5

0

21

2

Explanation

Два указателя.

Пусть

left = 1 # левый указатель;

right = n # правый указатель;

sum_left = 1 # сумма всех чисел от 1 до left;

sum_right = n # сумма всех чисел от right до n,

тогда пока два указателя не встретились, возможно три случая:

1) sum_left равен sum_right # найдено ещё одно решение, оба указателя смещаются на одну позицию навстречу друг другу, суммы увеличиваются на новые слагаемые;

2) sum_left меньше sum_right # левый указатель смещается на одну позицию, sum_left увеличивается на новое слагаемое;

3) sum_left больше sum_right # правый указатель смещается на одну позицию, sum_right увеличивается на новое слагаемое.