Island

Time limit3sMemory limit512 MB

Summary

Given the edge lengths of a cycle, find the maximum over all pairs of towns of the shorter of the two arc distances.

Level: Medium5 of 10
Topics: Two pointers, Prefix sum, Array
Solved: No attempts yet

Problem

On the island of Byteland, every town lies along the seashore, and the towns are arranged in a ring. A single two-way ring road runs along the coast and links all the towns in order, so from any town you can reach any other town by traveling either clockwise or counterclockwise around the ring. The distance between two towns is defined as the length of the shorter of these two routes.

Fans of two rival football teams want to watch the match from towns that are as far apart as possible. Determine the largest distance that can separate two towns on the island.

Write a program that:

reads a description of the island from standard input,
computes the maximum possible distance between any two towns,
writes that distance to standard output.

Input

The first line contains one integer $n$ ( $2 \le n \le 50000$ ), the number of towns, numbered $1$ through $n$ in order around the ring.

Each of the next $n$ lines contains one positive integer giving the length of a ring-road section. For $1 \le i \le n-1$ , line $i+1$ contains the length of the road between town $i$ and town $i+1$ . Line $n+1$ contains the length of the road between town $n$ and town $1$ .

The total length of the ring road does not exceed $10^9$ .

Output

Print one integer: the maximum distance that can separate two towns.

Examples2

Example 1
Input
```
5
1
2
3
4
5
```
Expected output
```
7
```
Example 2
Input
```
2
3
7
```
Expected output
```
3
```