Kangho the Part-Time Worker

Time limit2sMemory limit256 MB

Summary

Given N customers each with a planned tip, choose the serving order to maximize the total tip after subtracting (position-1) from each tip and clipping negative values to zero.

Level: Hard8 of 10
Topics: Greedy, Heap, Sorting, Math
Solved: No attempts yet

Problem

Starbox keeps its customers waiting in a line at the door until 8:00 a.m. At exactly 8:00 a.m., each customer receives one coffee at the entrance and then goes to a seat. Kangho is responsible for handing out the coffee at the entrance.

Each customer gives Kangho a tip based on the order in which they receive coffee. If a customer originally planned to give t won and receives coffee in position r, the actual tip is t - (r - 1) won. If this value is negative, the customer gives no tip.

For example, suppose three customers planned to give 3 won, 2 won, and 1 won, and they receive coffee in that order. Their actual tips are 3 won, 1 won, and 0 won, so Kangho receives 4 won in total.

Given N customers and the tip each customer originally planned to give, determine the maximum total tip Kangho can receive by choosing the order of the customers.

Input

The first line contains the number of customers N. N is a positive integer not greater than 100,000.

Each of the next N lines contains the tip one customer originally planned to give. Each tip is a positive integer not greater than 100,000.

Output

Print the maximum total tip Kangho can receive.

Examples5

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