27184번 - Campfire Riddle 다국어

One day Yurik found himself in a forest near the campfire where $n$ people had gathered.

It turned out that some of them are friends. Let's number all people with integers from $1$ to $n$. Let's denote the number of people that are friends with the $i$-th person, as $d_i$. It suddenly turned out that two people with numbers $i$ and $j$ ($i \ne j$) are friends if and only if $d_i = d_j$.

When Yurik came home he got curious, what is the minimum number of pairs of people that could be friends, so that the condition described above to be satisfied?

The only line contains one integer $n$ ($1 \le n \le 5\,000$) --- the number of people.

Print one integer --- the minimum number of pairs of friends.

Consider the first example. All possible cases are described below:

1. Each two people are friends with each other. In this case the number of pairs of friends is $\frac{4 \cdot 3}{2} = 6$.
2. Three people are pairwise friends with each other, and the fourth person is not friend with anyone. In this case the number of pairs of friends is $3$.