406814: GYM102565 C Flash

Flash is a prisoner in Penguin's Cave. The Cave can be represented like a NxN matrix with the columns and lines numbered from 1 to N. Flash can be found in the cell (1,1). Flash can travel to the cell (i,j) only from the cell (i-1,j) or (i,j-1). Penguin told Flash that he will be freed only if he will solve an easy problem.

Penguin gives him all the numbers $$$d$$$ from 1 to N+N-2 and asks Flash to start from (1, 1) and to mark all cells that can be reached. A cell (i, j) can be reached if and only if (i, j) = (1, 1) or there is another cell (i', j') that can be reached and the Manhattan distance between (i', j') and (i, j) is $$$d$$$.

In the end, Penguin wants to know how many cells will be marked an odd number of times.

The first line of the input will contain a single number $$$N$$$. ($$$1 \leq N \leq 1.000.000.000$$$).

The output should contain a single line with a single number representing the number of cells that will be marked by an odd number of times.

4

5

233

1974

In the first example, Flash will count the cells: (1,2) , (2,1) , (2,4) , (3,3) and (4,2).