In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
Write a program which:
In the first line of the standard input there is one positive integer , , denoting the number of towns on the island. In the following lines there are the lengths of the highway sections between adjacent towns. Each of the lines contains one positive integer. In the line numbered there is the length of the highway section between the town number and the town number , while in the line numbered there is the length of the route between the towns and . The whole length of the highway does not exceed .
The first and only line of the standard output should contain one integer being the maximal distance the fans may be separated.
For the input data:
5 1 2 3 4 5
the correct result is:
Task author: Piotr Chrzastowski-Wachtel.