An alien group has attacked Kasukabe so whole city is in big trouble! All people (count is N) in Kasukabe try to run away so is Shinchan! They came across a bridge over a river, and that bridge has been cursed by aliens. Bridge will collapse when someone passes over it.

Shinchan as a legend calls an ultra legend Buri Buri Zaemon by his magic card. Buri Buri appears and suggests Shinchan that whenever a person having magic card in his hand passes over the bridge then it will not collapse but since bridge is fragile only maximum 2 persons at a time can pass over it (and one of them should have magic card in his hand). All citizens of Kasukabe have to go to other side of the river using bridge as quickly as possible. When two persons A and B pass over bridge, it takes MAX(time(A), time(B)) to get them on the other side of river (where time(i) is the time taken by ith person to pass over the bridge). Shinchan has an array of all time[] values of all citizens.

Find the minimum time in which they escape the bridge. (There is only one magic card)

Input

First line contains N, 1 <= N <= 100000.

Next line contains N integers, 1 <= time[i] <= 1000000000 for each 1 <= i <= N.

Output

Output the minimum time to get all persons over the other side of the river.

Example

Input:
4
1 2 5 10
Output:
17

Explanation

• 1 and 2 cross,
• 1 comes back,
• 5 and 10 cross,
• 2 comes back,
• 1 and 2 cross.

Total = 2 + 1 + 10 + 2 + 2 = 17.