Talent Show

Interview

Time limit1sMemory limit1024 MB

Summary

Given N skill levels, arrange the soldiers so that the first full skill plus each rise over the previous performer totals as much as possible.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Lunar New Year is here, so the unit is holding a talent show! The show runs in order, with one soldier performing at a time.

The show's chief organizer was planning the event based on each soldier's skill. The organizer worried that if the performer before was too good, the next performer would feel pressure and fail to show their real ability. So the organizer made this hypothesis. Let the skill levels in order be $a\_1, a\_2, \cdots, a\_n$ . For every $i$ with $2\leq i\leq N$ , the $i$ -th performer can show only $\max\left(0,a\_i-a\_{i-1}\right)$ of their skill. The soldier who performs first shows their full skill.

Under this hypothesis, the organizer wants to arrange the soldiers so that the total skill they can show is as large as possible. Find the maximum total skill that all soldiers can show when they are arranged in a suitable order.

Input

The first line contains the number of soldiers $N$ . $(1\leq N\leq 100\,000)$

The second line contains the skill levels $a\_i$ of the $N$ soldiers, separated by spaces. $(1\leq a\_i\leq 10\,000)$

Output

Print the maximum total skill that the soldiers can show when they are arranged in a suitable order.

Examples1

Example 1
Input
```
6
1 4 3 5 6 2
```
Expected output
```
12
```