마트료시카
면접 대비시간 제한1초메모리 제한1024 MB
크기가 주어진 N개의 인형을 크기가 연속된 정수를 이루는 묶음으로 나누어, 각 묶음의 (가장 큰 크기 곱하기 개수) 합의 최댓값을 구한다.
문제
인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다.
인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라.
하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶다.
N개의 인형을 모두 사용하여, 마트료시카들을 판매한다고 할 때, 하령이가 올릴 수 있는 최대 수익은 얼마인가?
입력
첫째 줄에 인형의 개수 N이 주어진다. (1 ≤ N ≤ 2 × 105)
둘째 줄에 하령이가 가지고 있는 인형들의 크기를 나타내는 N개의 정수 Xi가 공백으로 구분되어 주어진다. (1 ≤ X**i ≤ 105)
출력
하령이가 올릴 수 있는 최대 수익을 출력하시오.
정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.