Problem Description

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.

Input Format

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

Output Format

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

4

8

5

20

Hint

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