P15527 [ROIR 2015 Day 2] circle Circular Line

In the city where Andrei and Boris live, the metro consists of a single circular line. Along this line, $n$ stations are placed at equal distances and are numbered from $1$ to $n$. The segment between two neighboring stations is called an interval. Trains on the circular line can travel clockwise or counterclockwise. Therefore, to get from one station to another, a passenger can choose the direction that passes through fewer intervals. The minimum number of intervals needed to travel from one station to another is called the distance between the two stations. The friends noticed the following property: if we fix a station $X$ and write down two numbers, $D_a$ — the distance from Andrei’s home station to station $X$, and $D_b$ — the distance from Boris’s home station to station $X$, then the obtained pair $[D_a, D_b]$ uniquely determines station $X$. For example, if $n = 4$, Andrei lives at station $1$, and Boris lives at station $2$, then station $1$ is represented by $[0, 1]$, station $2$ by $[1, 0]$, station $3$ by $[2, 1]$, and station $4$ by $[1, 2]$. Their classmate Sergey lives in a nearby city and does not know which stations Andrei and Boris live at. To find his friends, he is interested in how many ordered pairs of stations $A, B$ there are such that, if Andrei lives at station $A$ and Boris lives at station $B$, the property above holds. **Task**: Write a program that, given the number of stations $n$ on the circular line, determines the number of station pairs that satisfy the property.

The first line of the input file contains one integer $n$ ($3 \leq n \leq 40,000$).

The output file should contain one integer — the number of station pairs found.

### Example explanation In the first example, the station pairs that satisfy the property are: * Andrei lives at station $1$, Boris lives at station $2$; * Andrei lives at station $1$, Boris lives at station $4$; * Andrei lives at station $2$, Boris lives at station $1$; * Andrei lives at station $2$, Boris lives at station $3$; * Andrei lives at station $3$, Boris lives at station $2$; * Andrei lives at station $3$, Boris lives at station $4$; * Andrei lives at station $4$, Boris lives at station $1$; * Andrei lives at station $4$, Boris lives at station $3$. ### Scoring system and subtasks #### Subtask 1 (25 points) $3 \leq n \leq 50$. #### Subtask 2 (25 points) $3 \leq n \leq 500$. #### Subtask 3 (50 points) $3 \leq n \leq 40,000$. Translation source: GPT 5.2. Translated by ChatGPT 5