暂无测试数据。

有 $n$ 个小动物，形成一个环，按照顺时针的编号为 $1,2,\cdots,n$。

蒜头君会执行以下 $n$ 种操作。 每个操作都可以执行任意次数（可能为零）次。

• 支付 $a_1$ 元，给动物 $1,2$ 喂食物；
• 支付 $a_2$ 元，给动物 $2,3$ 喂食物；
• ...
• 支付 $a_{n-1}$ 元，给动物 $n-1,n$ 喂食物；
• 支付 $a_n$ 元，给动物 $n,1$ 喂食物；

问至少喂食每只动物一次的最低可能总成本。

输入格式

第一行一个整数 $n(2\leq n \leq 3\times 10^5)$，表示动物的数量。

第二行以空格隔开的正整数 $a_i(1\leq a_i \leq 10^9)$，含义如上。

输出格式

输出共一行，一个整数，表示至少喂食每只动物一次的最低可能总成本。

5
2 5 3 2 5

7