在比特兰（Byteland），计划举行一场两支敌对足球队——Linuxers 队和 Microsofters 队之间的比赛。由于两队球迷对彼此有着极深的敌意，他们只能通过电视观看比赛，并且应该分别位于彼此距离尽可能远的两座城市中。比特兰是一个岛屿，所有的城市都坐落在海岸线上。一条连接所有城市的双向高速公路沿着海岸延伸。从任意一座城市出发，都可以通过顺时针或逆时针方向到达其他任何城市。两条路线中较短的那条路线的长度即为这两座城市之间的距离。

任务

编写一个程序：

• 从标准输入读取岛屿的描述，
• 计算两队球迷之间可能的最大距离，
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个正整数 $n$（$2 \le n \le 50\,000$），表示岛上的城市数量。

接下来的 $n$ 行包含相邻城市之间高速公路路段的长度。每行包含一个正整数。第 $i+1$ 行表示城市 $i$ 与城市 $i+1$ 之间的高速公路路段长度，而第 $n+1$ 行表示城市 $n$ 与城市 $1$ 之间的路段长度。高速公路的总长度不超过 $1\,000\,000\,000$。

输出格式

标准输出的第一行且仅有一行应包含一个整数，表示两队球迷之间可能的最大距离。

样例

输入样例 1

5
1
2
3
4
5

输出样例 1

7