现有 $n$ 名小朋友围成一个圈，假设第 $i$ 名小朋友顺时针方向相邻的小朋友是第 $i \ \% \ n +1$ 名小朋友。

定义：

• $dis_a(i,j)$ 为第 $i$ 名小朋友沿圆圈顺时针走到第 $j$ 名小朋友所需路程距离。
• $dis_b(i,j)$ 为第 $i$ 名小朋友沿圆圈逆时针走到第 $j$ 名小朋友所需路程距离。

求出：

$\max_{1 \leq i,j \leq n}(\min(dis_a(i,j),dis_b(i,j)))$

第一行一个整数 $n \ (1 \leq n \leq 10^5)$。

接下来 $n$ 个数 $dis_a(1,2),dis_a(2,3),...,dis_a(i,i \ \% \ n +1),...,dis_a(n,1)$。

$1 \leq dis_a(i,i \ \% \ n +1) \leq 10^9$。

一个整数，表示答案。