该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有N个人，每个人有个权值，要围成一个圆环，于是他们一个个加入圆环中。但加入的位置由你来确定。

每当一个人加入圆环，但带来的快乐值为他左右两边的人的权值的较小值。

当然第一个人加入时，其左右两边是没有人的，于是带来的快乐值为0

当加入后面的人时候，就均会带来快乐值了.

现希望得到最大的快乐值，请问是多少。

Format

Input

第一行给出N

第二行给出N个数字，权值<=1e9

N<=1e5

Output

如题

Samples

4
2 2 1 3

7

10
10 9 8 7 6 5 4 3 2 1

70

Hint 对于样例1

得到的快乐值为

0+3+2+2=7

对于样例2