当前没有测试数据。

E - 高橋和动物

评分：500分

问题描述

Takahashi有N只动物。

这N只动物被称为动物1、动物2、...、动物N。

Takahashi将执行以下N种操作。每个操作可以执行任意次数（可能为零）。

1. Pay A1日元（日本的货币）来喂养动物1和动物2。
2. Pay A2日元来喂养动物2和动物3。
3. Pay A3日元来喂养动物3和动物4。 ... ... ...
4. Pay Ai日元来喂养动物i和动物（i+1）。 ... ...
5. Pay AN-2日元来喂养动物（N-2）和动物（N-1）。
6. Pay AN-1日元来喂养动物（N-1）和动物N。
7. Pay AN日元来喂养动物N和动物1。

注意，第N个操作上述喂养“动物N和动物1”。

打印至少喂养每只动物一次的最小总费用。

限制条件

• 2 ≤ N ≤ 3 × 10^5
• 1 ≤ Ai ≤ 10^9
• 输入中的所有值均为整数。

输入

输入输入来自标准输入，格式如下：

N

A1 A2 ... AN

输出

打印至少喂养每只动物一次的最小总费用。

5
2 5 3 2 5

7

如果Takahashi每个都执行一次第1，第3和第4个操作，分别喂食动物1、2、3、4、5一次、一次、一次、两次和一次，那么每只动物至少得到了一次喂食。

这样做的总费用为A1 + A3 + A4 = 2 + 3 + 2 = 7日元，这是可能的最小值。

20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

426