Trong thời gian ôn thi vất vả, AliVu nghĩ ra một trò chơi để giải trí cho bản thân và các bạn trong đội tuyển như sau:

Có ~N~ con chim đậu thành một hàng và con thứ ~i~ có sức mạnh là ~a_i~ với ~1≤a_i≤10^9~. Những con chim rất đoàn kết, vì vậy khi bạn bắn con chim nào thì con chim đậu liền trước và liền sau nó sẽ cùng với nó hợp sức lại chống trả (nếu nó đậu đầu của hàng thì chỉ có một chim liền trước hoặc liền sau thôi). Khi đó, bạn sẽ tốn ~a_{i-1}+a_i+a_{i+1}~ năng lượng để bắn được con chim thứ ~i~. Chú ý rằng sau khi con chim thứ ~i~ bị bắn thì các con chim còn lại sẽ đứng xích lại gần nhau thành 1 hàng liên tiếp.

AliVu luôn bắn con chim có sức mạnh lớn nhất, nếu có nhiều con cùng có sức mạnh lớn nhất, anh ta sẽ bắn con có số thứ tự nhỏ nhất. Vũ sẽ bắn cho đến khi lũ chim chết hết anh ta sẽ giàu to. Tuy nhiên anh không mang theo máy tính nên không biết mình sẽ mất bao nhiêu năng lượng. Hãy giúp AliVu nhé!

Input

• Dòng 1: Chứa số nguyên dương ~N~ với ~1 \le N \le 10^6.~
• Dòng 2: Gồm ~N~ số nguyên dương ~a_i~.

Output

• Một dòng duy nhất ghi năng lượng cần dùng.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

25

Sample Input 2

5
3 2 4 3 1

Sample Output 2

24

Giải thích

• Ở test VD1, Vũ cần tốn năng lượng là ~(5+4)+(4+3)+(3+2)+(2+1)+1=25~.
• Ở test VD2, Vũ cần tốn năng lượng là ~(4+2+3)+(3+2)+(2+3+1)+(2+1)+1=24~.

Giới hạn:

• Subtask 1: 25% test có ~N≤10^3~.
• Subtask 2: 25% test có ~N≤10^5~.
• Subtask 3: 25% test có ~a_i≤10^6~.
• Subtask 4: 25% test còn lại không có giới hạn thêm.