#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, a[N], ans = 2e9, bound[N], val[N];
vector<pair<int, int>> in[N], out[N];
multiset<int> st;
set<int> id;
struct node {
  int mn[2];
  node(int a = 2e9, int b = 2e9) {
    mn[0] = a;
    mn[1] = b;
  }
  node operator+(const node &a) {
    node ret;
    ret.mn[0] = min(mn[0], a.mn[0]);
    ret.mn[1] = min(mn[1], a.mn[1]);
    return ret;
  }
} seg[4 * N];
void find(int by) {
  st.clear();
  id.clear();
  for (int i = 1; i <= n; i++) {
    while (in[i].size()) {
      id.insert(in[i].back().second);
      st.insert(in[i].back().first);
      in[i].pop_back();
    }
    while (out[i].size()) {
      id.erase(out[i].back().second);
      st.erase(st.find(out[i].back().first));
      out[i].pop_back();
    }
    if (id.size()) bound[i] = min(bound[i], *id.begin());
    if (st.size()) val[i] = min(val[i], *st.begin() + by * i);
  }
}
void build(int c, int l, int r) {
  if (l == r) {
    seg[c].mn[0] = a[l] - l;
    seg[c].mn[1] = a[l] + l;
    return;
  }
  build(2 * c + 1, l, (l + r) / 2);
  build(2 * c + 2, (l + r) / 2 + 1, r);
  seg[c] = seg[2 * c + 1] + seg[2 * c + 2];
}
int get(int c, int l, int r, int s, int e, bool type) {
  if (l > e || r < s) return 2e9;
  if (l >= s && r <= e) return seg[c].mn[type];
  return min(get(2 * c + 1, l, (l + r) / 2, s, e, type),
             get(2 * c + 2, (l + r) / 2 + 1, r, s, e, type));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    bound[i] = 1e9;
    val[i] = 2e9;
  }
  build(0, 1, n);
  for (int i = 1; i <= n; i++) {
    int temp = 2 * i - a[i];
    if (temp > i) {
      in[i].push_back({a[i] - i, i});
      if (temp <= n) out[temp].push_back({a[i] - i, i});
    }
  }
  find(1);
  for (int i = 1; i <= n; i++)
    if (a[i] < i) {
      in[a[i] + 1].push_back({a[i] + i, i});
      out[i + 1].push_back({a[i] + i, i});
    }
  find(-1);
  for (int i = 1; i <= n; i++)
    if (bound[i] != 1e9) {
      ans = min(ans, max(val[i], get(0, 1, n, 1, min(bound[i] - 1, i), 0) + i));
      if (bound[i] > i)
        ans = min(ans, max(val[i], get(0, 1, n, i, bound[i] - 1, 1) - i));
    }
  if (ans > 3e5) ans = -1;
  printf("%d\n", ans);
}
