现有 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。

一个整数，表示答案。