CF955E Icicles

Andrew 最喜欢的 Krakozyabra 最近逃跑了，现在他渴望把它带回来！ 此刻，Krakozyabra 躲在一个冰冷的洞穴中，洞顶上悬挂着 $n$ 根冰柱，冰柱的位置为 $1$ 到 $n$ 的整数坐标。第 $i$ 根冰柱距离地面的距离为 $a_{i}$。 Andrew 可以自由选择一个 $T$，$T$ 是 $1$ 到 $n$ 之间的任意整数点，并在时刻 $0$ 从该点发射一个声波，声波以每秒一个点的速度向左右两侧传播。任何被声波触及的冰柱会以相同的速度开始下落（即每秒距离地面减少 $1$，但不会小于 $0$）。只要冰柱距离地面的距离大于 $0$，就可以通过；一旦距离变为 $0$，该冰柱就会掉落并阻挡通路。 Krakozyabra 最初（即在时刻 $0$）位于点 ，并以每秒一个点的速度向右奔跑。你可以假设在同一秒内事件的发生顺序如下：首先 Krakozyabra 先移动，然后声波传播并使冰柱下落；特别地，这意味着如果 Krakozyabra 当前在点 ，而该点的冰柱已经被声波触及且距离地面为 $1$，那么 Krakozyabra 会先通过该点到达 ，之后冰柱才会掉落并阻挡通路。 当 Krakozyabra 当前所在位置的左侧和右侧都出现掉落（即 $a_{i}=0$）的冰柱时，Krakozyabra 被认为被困住了。请你帮 Andrew 通过选择最优的 $T$，计算最短需要多少时间才能困住 Krakozyabra。如果无法完成任务，输出 $-1$。

第一行包含一个整数 $n$，表示冰柱的数量，$2 \leq n \leq 10^{5}$。 第二行包含 $n$ 个用空格分隔的整数 $a_{i}$，表示每根冰柱距离地面的距离，$1 \leq a_{i} \leq 10^{5}$。

输出一个整数，表示困住 Krakozyabra 所需的最短时间。如果无法完成任务，输出 $-1$。

在样例一中，最优的做法是在第 $3$ 个点发射声波。这样两秒后，第 $1$ 和第 $5$ 根冰柱会开始下落，再过一秒它们就会掉落并阻挡通路。此时 Krakozyabra 会位于 。注意第 $3$ 根冰柱也会掉落，因此实际上左侧会有两根冰柱阻挡通路。 在样例二中，最优做法是在第 $2$ 个点发射声波，可以在 $2$ 秒内困住 Krakozyabra。 在样例四中，无法完成任务，答案为 $-1$。 由 ChatGPT 4.1 翻译