No.831 City Tour
Shuz*
tatyamProblem Statement
Fourier-kun is touring the cities of the country of Shuz.
The country of Shuz has $N$ cities, numbered $1,\ 2,\ 3,\ ...,\ N$.
Every pair of $2$ cities is connected by an expressway, and when $i \neq j$, traveling between cities $i,\ j$ costs a base fee of $(i \times j)$ yen one way.
In addition, when traveling from city $i$ to city $j$, an additional fee of $(j-i)$ yen is charged if $i \lt j$, and a discount of $(i-j)$ yen is applied if $i \gt j$.
That is, when $i \neq j$, traveling from city $i$ to city $j$ costs a total of $(i \times j)+(j-i)$ yen.
Fourier-kun wants to start from any city he likes and make a round trip through the cities of Shuz using the expressways.
Find the minimum fee required for Fourier-kun to visit all $N$ cities $1$ time each and return to the city where he started.
Constraints
- $1 \le N \le 2 \times 10^6$
- All inputs are integers
Input
The input is given from standard input in the following format.
$N$
Output
Output the minimum fee required for Fourier-kun to visit all the cities $1$ time each.
Sample
Sample 1
Input
3
Output
11
For example, one of the cheapest routes is as follows:
from city $2$ to city $1$: $1$ yen
from city $1$ to city $3$: $5$ yen
from city $3$ to city $2$: $5$ yen
The total is $11$ yen,
so output the total fee, $11$.
Sample 2
Input
1
Output
0
If there is only $1$ city, there is no need to tour the cities, so no fee is charged.
Sample 3
Input
200
Output
1353499
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。