Longest Separation Distance of Rival Fans

In the Information Kingdom, an island nation, all cities are built along the coast and connected by a bidirectional circular highway. Every two consecutive cities are connected by a road segment, and there are two possible paths between any two cities: one going in a clockwise direction and the other in a counterclockwise direction. The distance between two cities is defined as the shorter of these two paths, i.e.,

\( \min(D, T - D) \)

where \( D \) is the distance in one direction and \( T \) is the total circumference of the island.

Due to deep-seated animosity between the fans of two rival teams, they must be placed in two cities that are as far apart as possible. In addition, they are only allowed to watch the matches on TV. Your task is to compute the maximum achievable separation distance between the two groups of fans.

inputFormat

The first line contains an integer \( n \) (\( n \ge 2 \)), representing the number of cities around the island. The second line contains \( n \) space-separated positive integers, where the \( i \)-th integer denotes the distance between the \( i \)-th city and the \( (i+1) \)-th city (with the \( n \)-th city connecting back to the first city).

outputFormat

Output a single integer: the maximum separation distance between two cities, defined as the minimum of the clockwise and anticlockwise distances.

sample

4
1 2 3 4

5