흔적을 따라가라!

면접 대비

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

요약

n개의 정수가 주어질 때, 각 값을 등장 횟수 이하로만 사용해 비어 있지 않은 정사각 행렬을 만들고 대각합을 최대로 만든다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬, 수학, 배열
정답자: 아직 제출이 없습니다

문제

정사각 행렬 $B_{ij}$ 의 대각합은 주대각선에 위치한 원소 $B_{ii}$ 들의 합이다.

정수 수열 $a_i$ 가 주어진다. 이 수열의 수들을 비어 있지 않은 정사각 행렬 $B_{ij}$ 에 배치하여 대각합이 최대가 되도록 하려 한다. 이때 수 $x$ 가 수열 $a_i$ 에 정확히 $k$ 번 등장한다면, 행렬 $B_{ij}$ 에서 $x$ 는 $k$ 번 이하로 등장해야 한다.

입력

첫 번째 줄에는 수열 $a_i$ 의 길이를 나타내는 정수 $n$ 이 주어진다 ( $1 \le n \le 10^5$ ).

다음 $n$ 개의 줄에는 각각 하나의 정수가 주어지며, $i$ 번째 줄에는 수열 $a$ 의 $i$ 번째 원소 $a_i$ 가 주어진다 ( $-10^9 \le a_i \le 10^9$ ).

출력

행렬 $B$ 의 대각합의 최댓값을 정수 하나로 출력한다.

예제1

예제 1
입력
```
6
31
10
2021
-11
0
0
```
예상 출력
```
2052
```