#include <bits/stdc++.h>
using namespace std;
int const MAX = 100 * 1000 + 41;
int const INF = 1000 * 1000 * 1000 + 41;
int const REALANS = 1000 * 1000 * 100 + 41;
int n;
int a[MAX];
int ans;
struct Node {
  int x, v, p;
  Node(){};
  Node(int x, int v, int p) : x(x), v(v), p(p){};
  bool operator<(const Node &a) const { return x < a.x; };
};
struct Tree {
  int t[MAX * 4];
  vector<Node> a, b;
  int l, r, val, p;
  int pos[MAX];
  Tree(){};
  void build(int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = INF;
    } else {
      int tm = (tl + tr) / 2;
      build(v * 2 + 1, tl, tm);
      build(v * 2 + 2, tm + 1, tr);
      t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }
  }
  void build(vector<Node> v) {
    a = v;
    b = v;
    sort(b.begin(), b.end());
    build(0, 1, n);
    for (int i = 0; i <= (int)b.size() - 1; i++) {
      pos[b[i].p] = i + 1;
    }
  }
  int ask(int v, int tl, int tr) {
    if (l > tr || tl > r) return INF;
    if (l <= tl && tr <= r) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(ask(v * 2 + 1, tl, tm), ask(v * 2 + 2, tm + 1, tr));
  }
  int ask(int x) {
    int l = -1;
    int r = (int)b.size();
    while (r - l > 1) {
      int h = (l + r) / 2;
      if (b[h].x >= x) {
        r = h;
      } else {
        l = h;
      }
    }
    this->l = r + 1;
    this->r = n;
    return ask(0, 1, n);
  }
  void upd(int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = val;
    } else {
      int tm = (tl + tr) / 2;
      if (p <= tm) {
        upd(v * 2 + 1, tl, tm);
      } else {
        upd(v * 2 + 2, tm + 1, tr);
      }
      t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }
  }
  void push(int i) {
    p = pos[i];
    val = a[i - 1].v;
    upd(0, 1, n);
  }
};
int l[MAX];
int r[MAX];
Tree l1, l2, r1, r2;
bool fl[MAX];
void buildl() {
  for (int i = 1; i <= n; i++) {
    l[i] = INF;
  }
  int cur = INF;
  for (int i = 1; i <= n; i++) {
    if (cur <= a[i] - i) {
      fl[i] = false;
    } else {
      fl[i] = true;
      cur = a[i] - i;
    }
  }
  for (int i = 1; i <= n; i++) {
    while (false) {
    };
  }
  vector<Node> v;
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(a[i] - i * 2, a[i] - i, i));
  }
  l1.build(v);
  for (int i = 1; i <= n; i++) {
    if (fl[i]) {
      l1.push(i);
    }
    l[i] = min(l[i], l1.ask(-i) + i);
  }
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(a[i], a[i] + i, i));
  }
  l2.build(v);
  for (int i = n; i >= 1; i--) {
    if (fl[i]) {
      l2.push(i);
    }
    l[i] = min(l[i], l2.ask(i) - i);
  }
}
void buildr() {
  for (int i = 1; i <= n; i++) {
    r[i] = INF;
  }
  vector<Node> v;
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(i * 2 - a[i], a[i] - i, i));
  }
  r1.build(v);
  for (int i = 1; i <= n; i++) {
    r1.push(i);
    r[i] = min(r[i], r1.ask(i + 1) + i);
  }
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(-a[i], a[i] + i, i));
  }
  r2.build(v);
  for (int i = n; i >= 1; i--) {
    r2.push(i);
    r[i] = min(r[i], r2.ask(-i + 1) - i);
  }
}
void solve() {
  buildl();
  buildr();
  ans = INF;
  for (int i = 1; i <= n; i++) {
    ans = min(ans, max(l[i], r[i]));
  }
  if (ans > REALANS) {
    ans = -1;
  }
  printf("%d\n", ans);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  solve();
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

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 ai.

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 <image> 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 <image> 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 <image> and only after that the icicle will finally fall and block the path.

Krakozyabra is considered entrapped if there are fallen (i.e. with ai = 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 ai (1 ≤ ai ≤ 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.

Examples

Input

5
1 4 3 5 1


Output

3


Input

4
1 2 1 1


Output

2


Input

2
2 1


Output

3


Input

2
1 2


Output

-1

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 <image> 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int const MAX = 100 * 1000 + 41;
int const INF = 1000 * 1000 * 1000 + 41;
int const REALANS = 1000 * 1000 * 100 + 41;
int n;
int a[MAX];
int ans;
struct Node {
  int x, v, p;
  Node(){};
  Node(int x, int v, int p) : x(x), v(v), p(p){};
  bool operator<(const Node &a) const { return x < a.x; };
};
struct Tree {
  int t[MAX * 4];
  vector<Node> a, b;
  int l, r, val, p;
  int pos[MAX];
  Tree(){};
  void build(int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = INF;
    } else {
      int tm = (tl + tr) / 2;
      build(v * 2 + 1, tl, tm);
      build(v * 2 + 2, tm + 1, tr);
      t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }
  }
  void build(vector<Node> v) {
    a = v;
    b = v;
    sort(b.begin(), b.end());
    build(0, 1, n);
    for (int i = 0; i <= (int)b.size() - 1; i++) {
      pos[b[i].p] = i + 1;
    }
  }
  int ask(int v, int tl, int tr) {
    if (l > tr || tl > r) return INF;
    if (l <= tl && tr <= r) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(ask(v * 2 + 1, tl, tm), ask(v * 2 + 2, tm + 1, tr));
  }
  int ask(int x) {
    int l = -1;
    int r = (int)b.size();
    while (r - l > 1) {
      int h = (l + r) / 2;
      if (b[h].x >= x) {
        r = h;
      } else {
        l = h;
      }
    }
    this->l = r + 1;
    this->r = n;
    return ask(0, 1, n);
  }
  void upd(int v, int tl, int tr) {
    if (tl == tr) {
      t[v] = val;
    } else {
      int tm = (tl + tr) / 2;
      if (p <= tm) {
        upd(v * 2 + 1, tl, tm);
      } else {
        upd(v * 2 + 2, tm + 1, tr);
      }
      t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }
  }
  void push(int i) {
    p = pos[i];
    val = a[i - 1].v;
    upd(0, 1, n);
  }
};
int l[MAX];
int r[MAX];
Tree l1, l2, r1, r2;
bool fl[MAX];
void buildl() {
  for (int i = 1; i <= n; i++) {
    l[i] = INF;
  }
  int cur = INF;
  for (int i = 1; i <= n; i++) {
    if (cur <= a[i] - i) {
      fl[i] = false;
    } else {
      fl[i] = true;
      cur = a[i] - i;
    }
  }
  for (int i = 1; i <= n; i++) {
    while (false) {
    };
  }
  vector<Node> v;
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(a[i] - i * 2, a[i] - i, i));
  }
  l1.build(v);
  for (int i = 1; i <= n; i++) {
    if (fl[i]) {
      l1.push(i);
    }
    l[i] = min(l[i], l1.ask(-i) + i);
  }
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(a[i], a[i] + i, i));
  }
  l2.build(v);
  for (int i = n; i >= 1; i--) {
    if (fl[i]) {
      l2.push(i);
    }
    l[i] = min(l[i], l2.ask(i) - i);
  }
}
void buildr() {
  for (int i = 1; i <= n; i++) {
    r[i] = INF;
  }
  vector<Node> v;
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(i * 2 - a[i], a[i] - i, i));
  }
  r1.build(v);
  for (int i = 1; i <= n; i++) {
    r1.push(i);
    r[i] = min(r[i], r1.ask(i + 1) + i);
  }
  v.clear();
  for (int i = 1; i <= n; i++) {
    v.push_back(Node(-a[i], a[i] + i, i));
  }
  r2.build(v);
  for (int i = n; i >= 1; i--) {
    r2.push(i);
    r[i] = min(r[i], r2.ask(-i + 1) - i);
  }
}
void solve() {
  buildl();
  buildr();
  ans = INF;
  for (int i = 1; i <= n; i++) {
    ans = min(ans, max(l[i], r[i]));
  }
  if (ans > REALANS) {
    ans = -1;
  }
  printf("%d\n", ans);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  solve();
  return 0;
}

```