题目背景

在一个信息王国里决定在两个敌对的球队： LINUKS 和 MICROSOFT 之间举行球赛。

题目描述

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

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

现在，你需要计算出把敌对球迷分隔的最大距离。

输入格式

第一行输入一个正整数 $n$，表示海岛上城市的数目。

在接下来的 $n$ 行中输入相邻城市间环行公路的长度。每一行中包含了一个整数。

第 $i+1$ 行为 $i$ 的城市和编号为 $i+1$ 的城市之间公路段的长度，第 $n+1$ 行为城市 $n$ 和城市 $1$ 之间路程的长度。 环行公路的总长度不超过 $10^9$。

输出格式

一行一个数表示可以将球迷分隔的最大距离。

5
1
2
3
4
5

7

提示

对于 $100\%$ 的数据，$2\le n\le 50 000$。