D. The Beast's Shadowy Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Just when the three friends thought they were making progress through the Elderwood, a chilling presence descended. The air grew heavy, and the shadows seemed to twist into sinister forms. From the deepest part of the forest, the gravelly voice of the Beast echoed, its words seeping into their minds like cold mist.

"Welcome, little travelers," the Beast rumbled, its unseen form seemingly everywhere at once. "To truly test your cunning, you must play my game. Succeed, and your path may clear. Fail, and you shall wander these woods eternally."

A flat, obsidian stone appeared before them, acting as a "blackboard." On it, the Beast magically inscribed an even number $$$N$$$ copies of the number $$$1$$$.

"This is a game for two players," the Beast explained."One of you shall be Player A, the other Player B. In each round:

  • Player A chooses two numbers, $$$a$$$ and $$$b$$$, from the stone and erases them.
  • Player B then writes either their sum $$$(a + b)$$$ or their absolute difference $$$(|a - b|)$$$ back onto the stone.
The game would continue until one of two conditions was met:
  1. One of the numbers on the stone became larger than the sum of all other numbers currently on the stone.
  2. All numbers on the stone became zero.

"Now for the stakes," the Beast continued, a hint of cruel amusement in its voice."At the very end, Player B must give Player A a certain number of enchanted cookies. This number will be equal to the number of numbers remaining on the stone when the game ends."

"Player A," the Beast directed, its gaze seemingly fixed on Sam07a, "you wish to gain as many cookies as possible. Player B," it then turned its attention to Omar, "you wish to give as few as possible."

Sam07a and Omar looked at each other, a grim determination setting in. Abd-Elmohaymen, ever the supportive friend, quickly realized that this was a strategic game, and they needed to determine the outcome if both players played optimally. The cookies weren't just a prize; they were rumored to possess properties that could reveal hidden paths.

How many cookies will Player A (Sam07a) receive if both players play optimally in the Beast's shadowy game?

Input

A single $$$even$$$ integer $$$N$$$ $$$(2 \le N \le 10^7)$$$ the number of copies of $$$1$$$s.

Output

The number of cookies Player A (Sam07a) will receive if both players play optimally in the Beast's shadowy game .

Example
Input
2
Output
1
Note

In Player A's turn, Player A must choose the two numbers on the board: $$$a=1$$$, $$$b=1$$$. Both are erased and the board is empty now. No matter what Player B chooses (2 from (1+1)) or (0 from (1-1)) , the game terminates, and there is always exactly one number left on the board. Therefore, Player A receives 1 cookie.