| About Olympic -> Problems |  |
|
IX Olimpiada Informatyczna 2001/2002
|
|
Task: wys
|
Author: Piotr Chrz±stowski-Wachtel
|
Island
| I stage contest |
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 5the correct answer is in the following output file wys.out:
7
Print friendly version