P5942 [POI 2002] Rival Fans.

In an information kingdom, it is decided to hold a football match between two rival teams: LINUKS and MICROSOFT.

Because the fans of the two teams hate each other deeply, they must be arranged in two cities as far apart as possible, and they are only allowed to watch the match on TV. The information kingdom is an island country, and all its cities are built on the coast. Along the shoreline of the island, there is a two-way circular road. There are two ways to travel from any city to another city: clockwise and counterclockwise. In this two-way circular road system, the shorter of the two distances is defined as the distance between the two cities. Now, you need to compute the maximum distance by which the rival fans can be separated.

The first line contains a positive integer $n$, representing the number of cities on the island. In the next $n$ lines, each line contains an integer, describing the length of the circular road segment between two adjacent cities. Line $i+1$ gives the length of the road segment between city $i$ and city $i+1$, and line $n+1$ gives the length of the road segment between city $n$ and city $1$. The total length of the circular road does not exceed $10^9$.

Output one number in one line, representing the maximum distance by which the fans can be separated.

For $100\%$ of the testdata, $2\le n\le 50 000$. Translated by ChatGPT 5