Đề bài

Trong thời gian ôn thi vất vả, BigZ 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~ (~1 \leq N \leq 10^6~) con chim đậu thành một hàng. Con thứ ~i~ có sức mạnh là ~a[i]~ (~1 \leq a[i] \leq 10^9~). Những con chim rất đoàn kết, vì vậy khi bạn bắn con chim thứ ~i~, thì 3 con chim ~i - 1~ (nếu ~i > 1~), ~i~, ~i + 1~ (nếu ~i < N~) sẽ hợp sức lại chống trả. Vì vậy bạn mất ~a[i - 1] + a[i] + a[i + 1]~ năng lượng để bắn chết con chim thứ ~i~. Sau đó, các con chim còn lại đứng xích lại gần nhau thành một hàng liền kề.

BigZ 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. 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 BigZ!

Input

• Dòng 1: Chứa số nguyên dương ~N~.
• 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.

Ví dụ

Sample Input 1

5
1 2 3 4 5

Sample Output 1

25

Giới hạn

• Thời gian: 2.0s
• Bộ nhớ: 256M

Subtasks

• Subtask 1: 25% test có ~N \leq 1000~.
• Subtask 2: 25% test có ~N \leq 100000~.
• Subtask 3: 25% test có ~a[i] \leq 1000000~.
• Subtask 4: 25% test còn lại không có giới hạn thêm.