配点: $900$ 点

問題文

AtCoder さんは $2N$ 人の友人のために、円形のチョコレートケーキを作りました。このケーキは中心から放射状に $2N$ 個のピースに等分されており、各ピースには時計回りの順番で $0$ から $2N-1$ までの番号が付けられています。

いま、最後の仕上げとして、AtCoder さんはこのケーキの各ピースの上にいちごを乗せようとしており、そのために友人に希望を聞きました。友人には $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}$

出力

友人全員の希望を叶えるために乗せる必要のあるいちごの個数の最小値を出力してください。

3
2 5 7 4 2 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$ 個のいちごを置くことで、友人全員の希望を叶えることができます。 これが最小値となります。

3
8 0 6 0 9 0

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$ 個のいちごを置くことで、友人全員の希望を叶えることができます。 これが最小値となります。

5
3 1 5 7 0 8 4 6 4 9

12

ピース $0, 1, \dots, 9$ の上に置くいちごの個数を、それぞれ $0, 0, 0, 4, 0, 1, 1, 1, 0, 5$ とすると、友人全員の希望を叶えることができます。

このとき、チョコレートケーキ全体で $12$ 個のいちごを置くことになり、これが最小値となります。

1
267503 601617

869120

ピース $0$ の上に $267503$ 個、ピース $1$ の上に $601617$ 個のいちごを置くと、友人全員の希望を叶えることができます。

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

513119404