Matryoshka

Interview

Time limit1sMemory limit1024 MB

Summary

Partition N dolls into groups, each group being a consecutive range of distinct sizes, and maximize the sum over groups of (largest size) times (group size).

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

Haryeong, a doll collector, has N hollow dolls. The size of each doll is Xi.

Since the dolls are hollow, one doll can be placed inside another, and dolls of different sizes can be combined to form a matryoshka. Precisely, let Q be the size of the largest doll, W the size of the smallest doll, and T the number of dolls. A set of dolls satisfying (Q - W + 1 = T) is called a matryoshka. Note that a matryoshka may consist of a single doll.

The price of one matryoshka is set to Q × T. Haryeong wants to combine the dolls she has into matryoshkas to earn the maximum profit.

If she sells matryoshkas using all N dolls, what is the maximum profit she can earn?

Input

The first line gives the number of dolls N. (1 ≤ N ≤ 2 × 105)

The second line gives N integers Xi, the sizes of the dolls Haryeong has, separated by spaces. (1 ≤ Xi ≤ 105)

Output

Print the maximum profit Haryeong can earn.

Because the answer can exceed the range of a 32-bit integer variable (int), you must use a 64-bit integer variable (C/C++ : long long, JAVA : long).

Examples2

Example 1
Input
```
6
1 3 4 5 7 8
```
Expected output
```
32
```
Example 2
Input
```
7
5 3 4 10 4 8 9
```
Expected output
```
49
```