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.
## Input
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.
## Output
Print an only integer — the minimum time it takes to entrap Krakozyabra between two fallen icicles. If it is impossible, print - 1.
[samples]
## Note
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.
Let $ n $ be the number of icicles, and $ a_i \in \mathbb{Z}^+ $ be the initial height of the icicle at position $ i \in \{1, 2, \dots, n\} $.
Andrew chooses a launch point $ T \in \{1, 2, \dots, n\} $ at time $ t = 0 $. A sound wave propagates left and right from $ T $ at speed 1 unit per second. At time $ t $, the wave reaches all positions $ i $ such that $ |i - T| \leq t $. An icicle at position $ i $ begins to fall at time $ |i - T| $, and its height decreases by 1 per second thereafter. Thus, at time $ t \geq |i - T| $, the height of icicle $ i $ is $ \max(0, a_i - (t - |i - T|)) $.
The Krakozyabra starts at position $ T $ at time $ t = 0 $ and moves right at speed 1 per second. Thus, at time $ t $, it is at position $ T + t $.
An icicle at position $ i $ blocks passage at time $ t $ if its height becomes 0, i.e., if $ a_i - (t - |i - T|) \leq 0 $, or equivalently, $ t \geq a_i + |i - T| $.
Krakozyabra is entrapped at time $ t $ if:
- There exists some $ i < T + t $ such that $ t \geq a_i + |i - T| $ (an icicle to the left has fallen and blocks),
- There exists some $ j > T + t $ such that $ t \geq a_j + |j - T| $ (an icicle to the right has fallen and blocks).
We seek the **minimum** $ t \geq 0 $ such that there exists a $ T \in \{1, \dots, n\} $ for which the above two conditions hold simultaneously at time $ t $, and Krakozyabra is at $ T + t \in \{1, \dots, n\} $.
Define for each position $ i $ and launch point $ T $, the time at which icicle $ i $ blocks the path:
$$
f(i, T) = a_i + |i - T|
$$
Then, for fixed $ T $, define:
- $ L(T, t) = \exists i \leq T + t - 1 \text{ such that } f(i, T) \leq t $
- $ R(T, t) = \exists j \geq T + t + 1 \text{ such that } f(j, T) \leq t $
We want:
$$
\min_{T \in [1, n]} \min \left\{ t \in \mathbb{Z}_{\geq 0} : L(T, t) \land R(T, t) \right\}
$$
If no such $ T $ and $ t $ exist, return $ -1 $.
---
**Formal Statement:**
Given:
- $ n \in \mathbb{Z} $, $ 2 \leq n \leq 10^5 $
- $ a = [a_1, a_2, \dots, a_n] \in \mathbb{Z}_{>0}^n $
Define:
- $ f(i, T) = a_i + |i - T| $ for $ i, T \in \{1, \dots, n\} $
Find:
$$
\min_{T=1}^{n} \min \left\{ t \in \mathbb{N}_0 : \exists i \leq T + t - 1 \text{ s.t. } f(i, T) \leq t \text{ and } \exists j \geq T + t + 1 \text{ s.t. } f(j, T) \leq t \right\}
$$
If the set of valid $ (T, t) $ pairs is empty, output $ -1 $.