问题陈述

Mr. AtCoder为他的$2N$个朋友做了一个圆形巧克力蛋糕。它从中心被切割成$2N$个等分，按照顺时针顺序编号为0到$2N-1$。

为了最后的装饰，他打算在每一块上放草莓。他听说了朋友们对此的要求。朋友们从0到$2N-1$编号，第$i$个朋友（$0 \leq i \leq 2N-1$）想要以下内容：

• 第$i, i+1, \dots, i+N-1$块上的草莓总数至少是$A_i$（对于$x \geq 2N$，将第$x$块视为第$x-2N$块）。

为了满足所有朋友的要求，至少需要在整个蛋糕上放多少草莓？

约束条件

• $1 \leq N \leq 150000$
• $0 \leq A_i \leq 5 \times 10^8 \ (0 \leq i \leq 2N-1)$
• 输入中的所有值都是整数。

---

输入

输入以以下格式从标准输入给出：

$N$ $A_0$ $A_1$ $\cdots$ $A_{2N-1}$

输出

打印出满足朋友要求所需要放在整个蛋糕上的最少草莓数量。

---

示例输入1

3
2 5 7 4 2 1

示例输出1

8

考虑以下情况，我们分别在块0、1、2、3、4、5上放了1、0、1、4、2、0颗草莓。

在这种情况下，所有朋友的要求都得到满足，如下所示：

• 朋友0：块0、1、2上共有2颗草莓，不少于$A_0=2$。
• 朋友1：块1、2、3上共有5颗草莓，不少于$A_1=5$。
• 朋友2：块2、3、4上共有7颗草莓，不少于$A_2=7$。
• 朋友3：块3、4、5上共有6颗草莓，不少于$A_3=4$。
• 朋友4：块4、5、0上共有3颗草莓，不少于$A_4=2$。
• 朋友5：块5、0、1上共有1颗草莓，不少于$A_5=1$。

因此，我们可以在蛋糕上放入总共8颗草莓来满足所有朋友的要求。这是所需草莓数量的最小值。

---

示例输入2

3
8 0 6 0 9 0

示例输出2

12

考虑以下情况，我们分别在块0、1、2、3、4、5上放了6、0、2、1、3、0颗草莓。

在这种情况下，所有朋友的要求都得到满足，如下所示：

• 朋友0：块0、1、2上共有8颗草莓，不少于$A_0=8$。
• 朋友1：块1、2、3上共有3颗草莓，不少于$A_1=0$。
• 朋友2：块2、3、4上共有6颗草莓，不少于$A_2=6$。
• 朋友3：块3、4、5上共有4颗草莓，不少于$A_3=0$。
• 朋友4：块4、5、0上共有9颗草莓，不少于$A_4=9$。
• 朋友5：块5、0、1上共有6颗草莓，不少于$A_5=0$。

因此，我们可以在蛋糕上放入总共12颗草莓来满足所有朋友的要求。这是所需草莓数量的最小值。

---

示例输入3

5
3 1 5 7 0 8 4 6 4 9

示例输出3

12

我们可以分别在块0、1、$\dots$、9上放0、0、0、4、0、1、1、1、0、5颗草莓来满足所有朋友的要求。

在这种情况下，蛋糕上总共有12颗草莓，这是所需草莓数量的最小值。

---

示例输入4

1
267503 601617

示例输出4

869120

我们可以在块0上放267503颗草莓，在块1上放601617颗草莓来满足所有朋友的要求。

---

示例输入5

8
418940906 38034755 396064111 43044067 356084286 61548818 15301658 35906016 20933120 211233791 30314875 25149642 42550552 104690843 81256233 63578117

示例输出5

513119404