Farthest Cows on a Circle

Bessie's cows have formed a circle led by the clock hand. However, due to a lack of proper education, the spacing between adjacent cows is not uniform. The cows are curious to know what the maximum distance is between any two cows.

The distance between cow \(A\) and cow \(B\) is defined as the minimum of the clockwise distance and the counterclockwise distance between them. Given the distances between each pair of adjacent cows, let the total distance of the circle be \(T\). For any two cows, if the clockwise distance is \(d\), then the distance between them is \(\min(d, T-d)\). Your task is to compute the maximum such distance over all pairs of cows.

inputFormat

The input begins with an integer \(n\) representing the number of cows (and the number of distances). The next line contains \(n\) space-separated positive integers representing the distances between consecutive cows along the circle.

outputFormat

Output a single integer, which is the maximum distance (as defined) between any two cows on the circle.

sample

3
3 1 4

4