|
IX Olimpiada Informatyczna 2001/2002
|
|
Task: wys
|
Author: Piotr Chrz±stowski-Wachtel
|
Island
In Byteland there is a match planned between two antagonistic football
teams: the Linuxers and the Microsofters. Because the fans of both
teams are known to have a deep aversion to fans of the other team,
they should watch the match only on TV and ought to be located in
towns that are in the greatest possible distance to one
another. Byteland is an island, and all its towns lie along the
seashore. A two-way highway connecting all the towns runs along the
coast. From each town one can reach any other town going clockwise or
counterclockwise. The length of the shorter route is the distance
between the two towns.
Task
Write a program which:
- reads from the text file wys.in the description of the island,
- computes the maximal distance the fans of one team may be
separated from the fans of the other team,
- writes the result to the text file wys.out.
Input
In the first line of the text file wys.in there is one
positive integer n, 2<=n<=50 000, denoting the
number of towns on the island. In the following n lines
there are the lengths of the highway sections between adjacent
towns. Each of the lines contains one positive integer. In the line
numbered i+1 there is the length of the highway section between
the town number i and the town number i+1, while
in the line numbered n+1 there is the length of the route
between the towns n and 1. The whole length of the highway does
not exceed 1 000 000 000.
Output
The first and only line of the text file wys.out should
contain one integer being the maximal distance the fans may be
separated.
Example
For the following input file wys.in:
5
1
2
3
4
5
the correct answer is in the following output file wys.out:
7