JOI is planning to have a snack with his younger sisters, Joiko and Joimi. Today's snack is a baumkuchen, which is a favorite of all three.

A baumkuchen is a cylindrical cake, as shown in the figure below. To share it among the three, JOI must make three radial cuts to divide it into three pieces. However, since this baumkuchen is as hard as real wood, making cuts is not easy. Therefore, the baumkuchen already has $N$ notches, and JOI can only cut at the positions where these notches are located. When the notches are numbered 1 to $N$ in clockwise order, the size of the part between the $i$-th notch and the $(i+1)$-th notch is $A_i$ for $1 \le i \le N-1$, and the size of the part between the $N$-th notch and the 1st notch is $A_N$.

Figure 1: Example of a baumkuchen with $N = 6, A_1 = 1, A_2 = 5, A_3 = 4, A_4 = 5, A_5 = 2, A_6 = 4$

JOI, who is thoughtful of his sisters, decided that after cutting the baumkuchen into three pieces, he would choose the smallest piece for himself and give the remaining two pieces to his two sisters. On the other hand, since JOI loves baumkuchen, he wants to eat as much as possible. When he cuts the cake such that the size of the smallest piece is maximized, what will be the size of the piece that JOI eats?

Input

Read the following data from standard input:

• The first line contains an integer $N$, representing the number of notches on the baumkuchen.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $A_i$, representing the size of the part between the $i$-th notch and the $(i+1)$-th notch (if $i = N$, it is the size of the part between the $N$-th notch and the 1st notch).

Output

Output a single integer representing the maximum possible size of the smallest piece when the baumkuchen is divided into three pieces.

Constraints

All input data satisfies the following conditions:

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

Subtasks

1. (5 points) $N \le 100$
2. (15 points) $N \le 400$
3. (30 points) $N \le 8\,000$
4. (50 points) No additional constraints.

Examples

Input 1

6
1
5
4
5
2
4

Output 1

6

Figure 2: It is optimal to cut at the 1st, 3rd, and 5th notches.

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

Output 2

213