F - Gateau 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点: 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}

出力

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

入力例 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

Score : 900 points

Problem Statement

Mr. AtCoder made a round chocolate cake for his 2N friends. It is radially cut from the center into 2N equal pieces, numbered 0 through 2N-1 in clockwise order.

To give the final touches, he is going to put strawberries on each piece. He has heard what his friends want about it. The friends are numbered 0 through 2N-1, and Friend i (0 \leq i \leq 2N-1) wants the following:

  • Piece i, i+1, \dots, i+N-1 have a total of at least A_i strawberries on them (for x \geq 2N, consider Piece x as Piece x-2N).

To fulfill the requests of all his friends, at least how many strawberries should be put on the whole cake?

Constraints

  • 1 \leq N \leq 150000
  • 0 \leq A_i \leq 5 \times 10^8 \ (0 \leq i \leq 2N-1)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum number of strawberries that should be put on the whole cake to fulfill the requests of the friends.

Sample Input 1

3
2 5 7 4 2 1

Sample Output 1

8

Consider the case we put 1, 0, 1, 4, 2, 0 strawberries on Pieces 0, 1, 2, 3, 4, 5, respectively.

In this case, all requests of the friends are fulfilled, as follows:

  • Friend 0: Pieces 0, 1, 2 have a total of 2 strawberries on them, which is not less than A_0 = 2.
  • Friend 1: Pieces 1, 2, 3 have a total of 5 strawberries on them, which is not less than A_1 = 5.
  • Friend 2: Pieces 2, 3, 4 have a total of 7 strawberries on them, which is not less than A_2 = 7.
  • Friend 3: Pieces 3, 4, 5 have a total of 6 strawberries on them, which is not less than A_3 = 4.
  • Friend 4: Pieces 4, 5, 0 have a total of 3 strawberries on them, which is not less than A_4 = 2.
  • Friend 5: Pieces 5, 0, 1 have a total of 1 strawberry on them, which is not less than A_5 = 1.

Thus, we can fulfill all requests of the friends by putting a total of 8 strawberries on the cake. This is the minimum number of strawberries needed.

Sample Input 2

3
8 0 6 0 9 0

Sample Output 2

12

Consider the case we put 6, 0, 2, 1, 3, 0 strawberries on Pieces 0, 1, 2, 3, 4, 5, respectively.

In this case, all requests of the friends are fulfilled, as follows:

  • Friend 0: Pieces 0, 1, 2 have a total of 8 strawberries on them, which is not less than A_0 = 8.
  • Friend 1: Pieces 1, 2, 3 have a total of 3 strawberries on them, which is not less than A_1 = 0.
  • Friend 2: Pieces 2, 3, 4 have a total of 6 strawberries on them, which is not less than A_2 = 6.
  • Friend 3: Pieces 3, 4, 5 have a total of 4 strawberries on them, which is not less than A_3 = 0.
  • Friend 4: Pieces 4, 5, 0 have a total of 9 strawberries on them, which is not less than A_4 = 9.
  • Friend 5: Pieces 5, 0, 1 have a total of 6 strawberries on them, which is not less than A_5 = 0.

Thus, we can fulfill all requests of the friends by putting a total of 12 strawberries on the cake. This is the minimum number of strawberries needed.

Sample Input 3

5
3 1 5 7 0 8 4 6 4 9

Sample Output 3

12

We can put 0, 0, 0, 4, 0, 1, 1, 1, 0, 5 strawberries on Pieces 0, 1, \dots, 9, respectively, to fulfill all requests of the friends.

In this case, there is a total of 12 strawberries on the cake, which is the minimum number of strawberries needed.

Sample Input 4

1
267503 601617

Sample Output 4

869120

We can put 267503 strawberries on Piece 0 and 601617 strawberries on Piece 1 to fulfill all requests of the friends.

Sample Input 5

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

Sample Output 5

513119404