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 accross 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

Description:

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.

     |       |
(here persons are denoted by there crossing time.)
1,2,5,10  <-------> 
    total= 17