W Bajtlandii postanowiono zorganizować mecz pomiędzy dwiema zwaśnionymi drużynami piłkarskimi: Linuksowcami i Mikromiękkimi. Ponieważ kibice obu drużyn znani są z wzajemnej głębokiej antypatii, należy ich ulokować w miastach możliwie najdalej od siebie oddalonych i pozwolić na oglądanie meczu tylko w telewizji. Bajtlandia jest wyspą, a wszystkie jej miasta leżą na wybrzeżu. Wzdłuż brzegów wyspy biegnie dwukierunkowa autostrada, która łączy wszystkie miasta. Z każdego miasta do każdego innego można dojechać na dwa sposoby: w kierunku zgodnym z ruchem wskazówek zegara, i w kierunku przeciwnym. Długość krótszej z tych dróg jest odległością między miastami.

Zadanie

Napisz program który:

• wczyta z pliku tekstowego wys.in opis wyspy,
• obliczy maksymalną odległość na jaką mogą zostać odseparowani kibice,
• zapisze wynik w pliku tekstowym wys.out.

Wejście

W pierwszym wierszu pliku tekstowego wys.in zapisana jest jedna dodatnia liczba całkowita n, 2<=n<=50 000, oznaczająca liczbę miast znajdujących się na wyspie. W kolejnych n wierszach zapisano długości odcinków autostrady pomiędzy sąsiednimi miastami. Każdy z tych wierszy zawiera jedną dodatnią liczbę całkowitą. W wierszu o numerze i+1 zapisana jest długość odcinka autostrady pomiędzy miastem o numerze i, a miastem o numerze i+1, natomiast w wierszu o numerze n+1 zapisana jest długość drogi pomiędzy miastem n a 1. Całkowita długość autostrady nie przekracza 1 000 000 000.

Wyjście

Pierwszy i jedyny wiersz pliku tekstowego wys.out powinien zawierać jedną liczbę całkowitą oznaczającą maksymalną odległość na jaką mogą zostać odseparowani kibice.

Przykład

Dla pliku wejściowego wys.in:

5
1
2
3
4
5

7