Problem Description

JOI is planning to eat some sweets with his two younger sisters, JOI-ko and JOI-mi. Today’s sweet is their favorite: an annual ring cake (Baumkuchen).

An annual ring cake is a cylindrical sweet as shown in the figure below. To divide it among three people, JOI must make three cuts along the radial direction, splitting it into three pieces. However, this cake is as hard as real wood, so cutting it is not easy. Therefore, the cake already has $N$ notches, and JOI can only cut at positions where there is a notch. The notches are numbered clockwise from $1$ to $N$. For $1 \le i \le N-1$, the size of the part between notch $i$ and notch $i+1$ is $A_i$. Also, the size of the part between notch $N$ and notch $1$ is $A_N$.

:::align{center}

Figure 1: Example of an annual ring cake where $N = 6$, $A_1 = 1$, $A_2 = 5$, $A_3 = 4$, $A_4 = 5$, $A_5 = 2$, $A_6 = 4$ :::

Being considerate of his sisters, after cutting the cake into three pieces, JOI decides that he will take the smallest piece, and give the remaining two pieces to his two sisters. On the other hand, JOI loves Baumkuchen very much, so he wants to eat as much as possible. If he cuts the cake in a way that makes the smallest piece as large as possible, what will be the size of the piece that JOI eats?

Task

Given the number of notches $N$ and the integers $A_1, \dots, A_N$ representing the sizes of the parts, write a program to output the maximum possible value of the smallest piece size when the annual ring cake is cut into three pieces.

Input Format

Read the following data from standard input.

• Line 1 contains an integer $N$, indicating that there are $N$ notches on the annual ring cake.
• In the next $N$ lines, line $i$ ($1 \le i \le N$) contains an integer $A_i$, indicating that the size of the part between notch $i$ and notch $i+1$ (when $i = N$, between notch $N$ and notch $1$) is $A_i$.

Output Format

Output one line to standard output containing one integer: the maximum possible value of the smallest piece size when the annual ring cake is cut into three pieces.

6
1
5
4
5
2
4

6

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

213

Hint

Sample Explanation

:::align{center}

Figure 2: It is optimal to cut at notches $1$, $3$, and $5$. :::

Constraints

All input data satisfy the following conditions.

• $3 \le N \le 10^5$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)

Subtasks

Subtask 1 [5 points]

$N \le 100$.

Subtask 2 [15 points]

$N \le 400$.

Subtask 3 [30 points]

$N \le 8000$.

Subtask 4 [50 points]

No additional constraints.

Translation completed by DeepSeek V3.2.

Translated by ChatGPT 5