23845번 - 마트료시카

문제

인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 X_i이다.

인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라.

하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶다.

N개의 인형을 모두 사용하여, 마트료시카들을 판매한다고 할 때, 하령이가 올릴 수 있는 최대 수익은 얼마인가?

입력

첫째 줄에 인형의 개수 N이 주어진다. (1 ≤ N ≤ 2 × 10⁵)

둘째 줄에 하령이가 가지고 있는 인형들의 크기를 나타내는 N개의 정수 X_i가 공백으로 구분되어 주어진다. (1 ≤ X_i ≤ 10⁵)

출력

하령이가 올릴 수 있는 최대 수익을 출력하시오.

정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.

제한

힌트