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.
4
3
5
4
Consider the first example. All possible cases are described below:
Name |
---|