Campfire Riddle

시간 제한1초메모리 제한1024 MB

요약

n명에 대해 친구 수가 같은 사람끼리만 친구가 되도록 할 때 가능한 친구 쌍 개수의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

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:

Each two people are friends with each other. In this case the number of pairs of friends is $\frac{4 \cdot 3}{2} = 6$ .
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$ .

예제2

예제 1
입력
```
4
```
예상 출력
```
3
```
예제 2
입력
```
5
```
예상 출력
```
4
```