Two Towers

There are N points numbered 1 through N, connected in order around a circle. The distance of each segment between adjacent points is given. You will build one tower at each of two different points, and you want the distance between the two towers to be as large as possible.

For any two points, there are two paths around the circle: clockwise and counterclockwise. The distance between the towers is defined as the shorter of the two path lengths.

Find the maximum possible distance between the two towers.

The first line contains N (2 <= N <= 50,000).

Each of the next N lines contains the distance of one adjacent segment in order: between points 1 and 2, points 2 and 3, ..., and points N and 1. Each distance is a positive integer, and the sum of all distances is at most 1,000,000,000.

Print the maximum possible distance between the two towers.