bzoj#P2955. [Poi2002]敌对球迷

[Poi2002]敌对球迷

题目描述

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

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

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

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

输入格式

本题有多组测试数据。

第一行读入一个正整数 nn,表示城市的数量。

接下来 n1n-1 行,每行输入一个正整数,代表第 ii 和第 i+1i+1 个城市之间公路的长度 aia_i

最后一行输入一个正整数,代表第 nn 和第 11 个城市之间公路的长度 ana_n

输出格式

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

样例输入

5
1
2
3
4
5

样例输出

7

数据规模与约定

对于所有数据,n5×104n\leq 5\times10^4ai109\sum a_i\leq 10^9