Get Minimum Cost

Each time, choose any two of the first three elements of the current array and delete them; the cost of the operation is the larger of the two deleted numbers. If fewer than three elements remain, delete all the remaining elements at once, at a cost equal to their maximum. Find the minimum total cost to empty the array.

The standard input/output, the ranges added by this site, and the examples follow this problem's description.

输入格式

The first line contains n (1≤n≤1000); the second line contains n positive integers, 1≤arr[i]≤10^6. The ranges are taken from the original problem's constraints.

输出格式

Output the minimum total cost.

样例 1

输入：

1
7

输出：

7

样例 2

输入：

2
4 2

输出：

4

样例 3

输入：

5
1 2 3 4 5

输出：

9