Problem Description

JOI is going to have a snack with his sisters, JOI-chan and JOI-mi-chan. Today's snack is their favorite Baumkuchen.

Baumkuchen is a cylindrical pastry, as shown in the figure below. To divide it into three pieces, JOI needs to cut it three times along the radius. However, this Baumkuchen is as hard as real wood, so it's not easy to cut. Therefore, there are already $N$ notches on this Baumkuchen, and JOI can only cut at these notched positions. When the notches are numbered clockwise from 1 to $N$, for $1 \leq i \leq N - 1$, the size of the part between the $i$-th and $(i + 1)$-th notches is $A_i$. Also, the size of the part between the $N$-th notch and the 1st notch is $A_N$.

JOI, thinking of his sisters, decided to take the smallest piece after cutting the Baumkuchen into three pieces, and give the remaining two pieces to his sisters. On the other hand, JOI loves Baumkuchen and wants to eat as much as possible. What will be the size of the smallest piece when cut to maximize the size of the smallest piece?

Input Format

Read the following input from standard input:

• The first line contains an integer $N$, which represents the number of notches on the Baumkuchen.
• The next $N$ lines contain an integer $A_i$ each. This represents the size of the part between the $i$-th and $(i + 1)$-th notches (or between the $N$-th and 1st notches when $i = N$).

Output Format

Output the maximum size of the smallest piece when the Baumkuchen is divided into three pieces, as an integer on one line to standard output.

Sample Input and Output

Sample Input #1

6
1
5
4
5
2
4

Sample Output #1

6

Sample Input #2

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

Sample Output #2

213

Notes/Hints

Task

Given the number of notches $N$ and the sizes of each part represented by integers $A_1, \ldots, A_N$, create a program that outputs the maximum size of the smallest piece when the Baumkuchen is divided into three pieces.

Constraints

All input data satisfies the following conditions:

• $3 \leq N \leq 100,000$.
• $1 \leq A_i \leq 1,000,000,000$ ($1 \leq i \leq N$).

Subtasks

Subtask 1 [5 points]

$N \leq 100$.

Subtask 2 [15 points]

$N \leq 400$.

Subtask 3 [30 points]

$N \leq 8,000$.

Subtask 4 [50 points]

No additional constraints.

Sample Explanation 1

见题面 Input 部分

见题面 Output 部分