Hi,I tried to solve this problem during the contest but could not.Contest is over.Please Help

Basically it states that there are N numbers in an array A

initially sum=0

if i choose a number A[i] then i will add minimum of (A[i-1],A[i+1]) to my sum and will discard A[i] off the array,

Find such the maximum sum that can be obtained.Example

Input

5

1 1 4 2 5

Output

6

First of all, second element (1) will be removed. 1 will be added into the account, as min(1,4)=1. Remaining chips would be arranged as : 1 4 2 5.

Then fourth element (2) will be removed and 4 will be added into account. Remaining chips : 1 4 5.

Similarly proceed further. Final credits will be : 1+4+1 = 6.