问题 K: 小D分蛋糕

小D马上要和他的另外两个舍友一起吃小吃。今天的小吃是在迷宫里发现的那一块蛋糕，这一块蛋糕是像下图一样圆的蛋糕。为了把蛋糕分给三个人，小D必须沿着半径方向切3刀，从而把蛋糕分成三块。然而，由于这个快蛋糕在迷宫里放的太久了，已经硬得像实木一样，要让刀切进去并不简单。因此，这个蛋糕上事先准备了N个切口，而小D只能在有切口的位置下刀。切口按顺时针顺序编号为1到N，对于 ，第i个切口和第i+1个切口之间部分的大小是Ai。第N个切口和第1个切口之间部分的大小是 An。

小D在把蛋糕切成3块之后，为了照顾他可爱的舍友，自己选走最小的一块吃掉，把剩下两块分给两个舍友。而另一方面，小D太喜欢蛋糕了，只要能吃到的时候就会想吃很多很多。试求：小D吃掉的蛋糕的大小至多不超过多少。

给出切口个数N和表示各部分大小的整数 ，请求出把年轮蛋糕切成3块之后最小一块大小的最大值。

第 1 行一个整数 N，蛋糕上有 N 个切口；

接下来有 N 行，第 i行有一个整数 Ai，表示第 i 个切口和第 i+1 个切口之间部分的大小。

输出一行，一个整数，表示当把年轮蛋糕切块之后最小块大小的最大值。

6
1
5
4
5
2
4

6

3<=N<=100000

1<=Ai<=10^9