Give N bricks and a sequence a₁...a_n as the insulation of them. If we arrange the bricks in that order into a wall then the insulation of the wall is a₁ + a₂ + ... + a_N + max(0, a₂ - a₁) + max(0, a₃ - a₂) + ... + max(0, a_N - a_N - 1). Your task is to arrange the bricks so that the insulation of the wall is maximum.

Input

• The first line is N (1 <= N <= 10⁵).
• In each of the next N lines, the i^th line is a_i-1

Output

• The maximum insulation of the wall.

Example

Input:
4
5
4
1
7


Output:
24