Description

Grandma Xiong’s cows have formed a circle in clockwise order. Because they lack strict training, the gaps between adjacent cows are unequal.

The cows want to know how far apart the farthest pair of cows are. The distance from cow $A$ to cow $B$ is defined as the shorter of the clockwise path and the counterclockwise path from $A$ to $B$. Given the distances between adjacent cows, please compute the maximum distance between any two cows.

Input Format

The first line contains an integer $N$, the number of cows, $2\le N\le 10^5$.

The next $N$ lines each contain one integer. For $i=2,\ldots,N$, line $i$ contains $d_i$, the clockwise distance from cow $i-1$ to cow $i$, where $1\le d_i\le 2^{31}-1$, and the sum of all distances is $\le 2^{31}-1$.

Line $N+1$ contains the clockwise distance from cow $N$ to cow $1$.

Output Format

Output one line containing the maximum distance.

5
1
2
3
4
5

7

Hint

Translated by ChatGPT 5