题目描述

信息王国的两支球队 LINUKS 和 MICROSOFT 之间将会举行球赛。

由于两个球队的球迷结怨甚深，所以要将他们安排在两个距离尽量遥远的城市里，而且只允许他们从电视中看球赛。

信息王国是个岛国，它所有的城市都建在海岸上。沿着海岛周边有一条双向的环行公路。有两种方法可以从每一个城市到达另一个城市：顺时针和逆时针方向。这条双向环行公路中较短的距离是城市之间的距离。

你需要编写一个程序，计算可以分隔敌对球迷的最大距离。

输入格式

本题有多组测试数据。

第一行读入一个正整数 $n$，表示城市的数量。

接下来 $n-1$ 行，每行输入一个正整数，代表第 $i$ 和第 $i+1$ 个城市之间公路的长度 $a_i$。

最后一行输入一个正整数，代表第 $n$ 和第 $1$ 个城市之间公路的长度 $a_n$。

输出格式

输出一行，包含一个整数，即最长分隔距离。

样例输入

5
1
2
3
4
5

样例输出

7

数据规模与约定

对于所有数据，$n\leq 5\times10^4$，$\sum a_i\leq 10^9$。