You are the most notorious man Gabbar. Along with your gang, you want to loot a train, full of gold. Train has N bogies, including the engine. Each bogie has some gold in it. You will have N attempts, in each attempt you can choose one bogie and remove it from train. But here is a twist, when you remove a bogie, you don’t get the gold inside it, instead you get min(gold in left adjacent bogie, gold in right adjacent bogie) . If there is no left adjacent bogie or no right adjacent bogie, then you get 0 gold.

Once the bogie is removed from train, the two sections of train are again joined together by the driver.

Find the maximum gold that you can collect.

INPUT

First line contains single integer N.

Next line contain N integers, describing gold amount in each bogie (first integer is gold amount in first bogie).

OUTPUT

Single integer, maximum amount of gold.

CONSTRAINTS

1<=N<=5*10⁵

1<=A_i<=10⁶