题目内容

一条笔直的通信线路沿线分布着 $n$ 个终端，按顺序编号为 $1$ 到 $n$。第 $i$ 个终端需要至少 $r_i$ 的信号强度才能正常运作。

你计划在某个整数坐标 $c$（$1 \le c \le n$）处设置一座基站，并为其选定一个非负整数发射功率 $P$。信号在传输过程中会随距离衰减：位于 $i$ 的终端实际收到的信号强度为 $P - |i - c|$。为保证所有终端都满足需求，必须对每个 $i$ 都有 $P - |i - c| \ge r_i$。

你可以自由选择基站的位置 $c$。请计算在最优选址下，所需的最小发射功率 $P$。

终端数量 $n$ 不超过 200000，每个 $r_i$ 满足 $0 \le r_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示终端数量。 第二行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$，表示每个终端的最低信号需求，相邻整数之间以一个空格分隔。

输出描述

输出一行一个非负整数，表示所需的最小发射功率。

样例1

输入

3
1 2 3

输出

3

说明

我们有 3 个终端，需求 $r = [1, 2, 3]$。 计算 $A = \max_i(r_i + i) = \max(1+1, 2+2, 3+3) = 6$， $B = \max_i(r_i - i) = \max(1-1, 2-2, 3-3) = 0$。 最小功率 $P = \lceil \frac{A+B}{2} \rceil = \lceil \frac{6+0}{2} \rceil = 3$。 将基站设置在位置 $c = 3$，功率 $P = 3$： 终端 1 实际接收 $3 - |1-3| = 1 \ge 1$； 终端 2 接收 $3 - |2-3| = 2 \ge 2$； 终端 3 接收 $3 - |3-3| = 3 \ge 3$。 所有终端满足需求，因此最小功率为 3。

样例2

输入

1
0

输出

0

说明

边界情况：只有 1 个终端，需求为 0。 计算 $A = 0+1=1$，$B = 0-1=-1$，$P = \lceil \frac{1+(-1)}{2} \rceil = 0$。 最优选址 $c=1$，功率 0 即可满足需求。

样例3

输入

5
0 5 2 4 1

输出

6

说明

5 个终端，需求 $[0,5,2,4,1]$。 $A = \max(0+1, 5+2, 2+3, 4+4, 1+5) = \max(1,7,5,8,6) = 8$， $B = \max(0-1,5-2,2-3,4-4,1-5) = \max(-1,3,-1,0,-4) = 3$。 $P = \lceil \frac{8+3}{2} \rceil = 6$。 选择 $c=2$，验证： 终端 1 接收 $6-1=5 \ge 0$； 终端 2 接收 $6-0=6 \ge 5$； 终端 3 接收 $6-1=5 \ge 2$； 终端 4 接收 $6-2=4 \ge 4$； 终端 5 接收 $6-3=3 \ge 1$。 功率 6 可行，且是最小值。