CF955E.Icicles

Andrew's favourite Krakozyabra has recenly fled away and now he's eager to bring it back!

At the moment the refugee is inside an icy cave with n icicles dangling from the ceiling located in integer coordinates numbered from 1 to n. The distance between floor and the i-th icicle is equal to a__i.

Andrew is free to choose an arbitrary integer point T in range from 1 to n inclusive and at time instant 0 launch a sound wave spreading into both sides (left and right) at the speed of one point per second. Any icicle touched by the wave starts falling at the same speed (that means that in a second the distance from floor to icicle decreases by one but cannot become less that zero). While distance from icicle to floor is more than zero, it is considered passable; as soon as it becomes zero, the icicle blocks the path and prohibits passing.

Krakozyabra is initially (i.e. at time instant 0) is located at point and starts running in the right direction at the speed of one point per second. You can assume that events in a single second happen in the following order: first Krakozyabra changes its position, and only then the sound spreads and icicles fall; in particular, that means that if Krakozyabra is currently at point and the falling (i.e. already touched by the sound wave) icicle at point i is 1 point from the floor, then Krakozyabra will pass it and find itself at and only after that the icicle will finally fall and block the path.

Krakozyabra is considered entrapped if there are fallen (i.e. with a__i = 0) icicles both to the left and to the right of its current position. Help Andrew find the minimum possible time it takes to entrap Krakozyabra by choosing the optimal value of T or report that this mission is impossible.

安德鲁最喜爱的克拉科齐布拉最近逃走了，现在他急切地想要把它带回来！

目前，这只“逃犯”正身处一个冰窟中，洞顶悬挂着 $ n $ 根冰锥，它们位于整数坐标位置，编号从 $ 1 $ 到 $ n $。第 $ i $ 根冰锥距地面的距离为 $ a_i $。

安德鲁可以自由选择一个任意整数点 $ T $（满足 $ 1 \leq T \leq n $），并在时刻 $ 0 $ 发射一道声波；该声波以每秒一个单位的速度同时向左右两侧传播。一旦某根冰锥被声波触及，它便立即开始下落，下落速度也为每秒一个单位（即：每过一秒，该冰锥距地面的距离减 $ 1 $，但不会小于 $ 0 $）。只要冰锥距地面的距离严格大于 $ 0 $，它就被视为可通行；一旦该距离变为 $ 0 $，冰锥即落地并封锁路径，禁止通过。

克拉科齐布拉初始时刻（即时刻 $ 0 $）位于点 ，并以每秒一个单位的速度向右奔跑。你可以假设：每一秒内发生的事件按如下顺序进行——首先克拉科齐布拉移动位置，然后声波才继续传播、冰锥才继续下落；特别地，这意味着：若克拉科齐布拉当前位于点 ，而某根已被声波触及（即正在下落）的冰锥位于位置 $ i $、且此时距地面距离恰好为 $ 1 $，则克拉科齐布拉将顺利通过该位置，抵达 ，之后该冰锥才最终落地并封锁路径。

当克拉科齐布拉当前位置的左侧和右侧均存在已落地（即 $ a_i = 0 $）的冰锥时，它即被视为被困住。

请帮助安德鲁找出：通过选择最优的 $ T $ 值，使克拉科齐布拉被成功困住所需的最短时间；若该任务不可能完成，请报告这一点。

The first line contains the number of icicles n (2 ≤ n ≤ 105).

The next line contains n space-separated numbers a__i (1 ≤ a__i ≤ 105) — the distances from floor to icicles.

第一行包含冰柱的数量 $n$（$2 \leq n \leq 10^5$）。

第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^5$）——表示各冰柱底部到地面的距离。

Print an only integer — the minimum time it takes to entrap Krakozyabra between two fallen icicles. If it is impossible, print  - 1.

输出一个整数——将克拉科佐布拉困在两根坠落的冰柱之间的最短时间。若无法实现，则输出 -1。

In sample case one it's optimal to launch the sound wave from point 3. Then in two seconds icicles 1 and 5 will start falling, and in one more seconds they will block the paths. Krakozyabra will be located at at that time. Note that icicle number 3 will also be fallen, so there will actually be two icicles blocking the path to the left.

In sample case two it is optimal to launch the wave from point 2 and entrap Krakozyabra in 2 seconds.

In sample case four the answer is impossible.

在样例一中，最优策略是从位置 3 发射声波。这样，2 秒后冰锥 1 和 5 将开始下落，并再过 1 秒后便将路径完全封堵。此时 Krakozyabra 将位于 。注意：编号为 3 的冰锥也将落下，因此实际上将有两根冰锥封锁左侧通路。

在样例二中，最优策略是从位置 2 发射声波，可在 2 秒内将 Krakozyabra 困住。

在样例四中，答案不存在（即无解）。