Взять след!

면접 대비

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

요약

주어진 수를 중복 없이 사용해 정사각 행렬의 대각선에 배치할 때 가능한 최대 대각합을 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

Следом квадратной матрицы $B\_{ij}$ называется сумма элементов $B\_{ii}$ , расположенных на главной диагонали.

Дана последовательность целых чисел $a\_i$ . Требуется расставить числа из последовательности в непустую квадратную матрицу $B\_{ij}$ так, чтобы её след был максимально возможным. При этом, если число $x$ присутствует в последовательности $a\_i$ ровно $k$ раз, то в матрице $B\_{ij}$ оно должно присутствовать не более $k$ раз.

입력

Первая строка входных данных содержит одно целое число $n$ --- длину последовательности $a\_i$ ( $1 \le n \le 10^5$ ).

Последующие $n$ строк содержат по одному целому числу каждая, $i$ -я из них содержит $a\_i$ --- $i$ -й элемент последовательности $a$ ( $-10^9 \le a\_i \le 10^9$ ).

출력

Выведите одно целое число --- максимально возможное значение следа матрицы $B$ .

예제1

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