题目描述

熊大妈的奶牛在时针的带领下，围成了一个圆圈，由于没有严格的教育，奶牛们之间的间隔不一致。

奶牛想知道两只最远的奶牛到底隔了多远。奶牛 $A$ 到 $B$ 的距离为 $A$ 顺时针走和逆时针走，到达 $B$ 的较短路程。告诉你相邻两个奶牛间的距离，请你求出两只最远的奶牛到底隔了多远。

输入格式

第一行一个整数 $N$，表示有 $N$ 只奶牛，$2\le N\le 10^5$。

接下 $2\sim N+1$ 行，第 $i$ 行有一个数，表示第 $i-1$ 头奶牛顺时针到第 $i$ 头奶牛的距离 $d_i$，$1\le d_i\le 2^{31}-1$，所有距离之和 $\le 2^{31}-1$。

第 $N+1$ 行的数表示第 $N$ 头奶牛顺时针到第 $1$ 头奶牛的距离。

输出格式

一行，表示最大距离。

5
1
2
3
4
5

7