小Z去公园的时候，流浪猫都会来找他， n 只小猫围成一圈，小Z开始喂养流浪猫，小Z可以花费 a_i 喂食小猫 i 和 i+1。

需要注意的是，因为流浪猫围坐一圈，小Z可以花费 a_n 喂食动物 n 和 1。

输出喂食所有流浪猫需要的最小花费。

第一行一个数字n;

接下来一行是n个数字a_i

最小的花费

40%的数据： 2 ≤ N ≤20,1 ≤ a_i ≤ 10^9

100%的数据： 2 ≤ N ≤ 3 × 10^5,1 ≤ a_i ≤ 10^9