Ring Line
Time limit1sMemory limit1024 MB
Count ordered pairs of distinct stations A and B on a ring of n equally spaced stations such that the distance pair (dist from A, dist from B) is unique for every station.
- Level
Hard8 of 10
- Topics
- Math, Number theory, Combinatorics
- Solved
- No attempts yet
Problem
The subway in the city where friends Andrey and Boris live consists of a single ring line, along which n stations are placed at equal distances from each other and numbered from 1 to n. The segment of the subway line between two neighboring stations is called a span.
Trains on the ring line run both clockwise and counterclockwise, so to get from one station to another a passenger can choose the direction that requires passing fewer spans. The minimum number of spans that must be passed to get from one station to another is called the distance between the stations.
The friends noticed that the following condition holds: if you pick some station X and write down two numbers for it, Da, the distance from the station where Andrey lives to station X, and Db, the distance from the station where Boris lives to station X, then the resulting pair of numbers [Da, Db] uniquely determines station X.
For example, if n = 4, Andrey lives at station 1, and Boris lives at station 2, then station 1 is determined by the pair [0, 1], station 2 by the pair [1, 0], station 3 by the pair [2, 1], and station 4 by the pair [1, 2].
Their classmate Sergey lives in a neighboring city and does not know which stations Andrey and Boris live at. To find his friends, he wondered how many pairs of stations A, B exist such that if Andrey lives at station A and Boris lives at station B, the condition described above holds.
Write a program that, given the number of stations n on the ring line, determines the required number of options.
Input
The first line of the input contains a single integer n (3 ≤ n ≤ 40 000).
Output
The output must contain a single number: the required number of options.
Hint
In the first sample, the following options work:
- Andrey lives at station 1, and Boris at station 2;
- Andrey lives at station 1, and Boris at station 4;
- Andrey lives at station 2, and Boris at station 1;
- Andrey lives at station 2, and Boris at station 3;
- Andrey lives at station 3, and Boris at station 2;
- Andrey lives at station 3, and Boris at station 4;
- Andrey lives at station 4, and Boris at station 1;
- Andrey lives at station 4, and Boris at station 3.