Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built n towers in a row. The i-th tower is made of hi identical blocks. For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.

Input

The first line contains single integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers h1, h2, ..., hn (1 ≤ hi ≤ 109) — sizes of towers.

Output

Print the number of operations needed to destroy all towers.

Examples

Input

6
2 1 4 6 2 2


Output

3


Input

7
3 3 3 1 3 3 3


Output

2

Note

The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color. 

<image> After first operation there are four blocks left and only one remains after second operation. This last block is destroyed in third operation.
#include <bits/stdc++.h>
#pragma target("avx2")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
constexpr int INF = INT_MAX / 2;
constexpr long long LINF = LLONG_MAX / 2;
constexpr double eps = DBL_EPSILON;
constexpr double PI = 3.141592653589793238462643383279;
template <class T>
class prique : public std::priority_queue<T, std::vector<T>, std::greater<T>> {
};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return 1;
  }
  return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return 1;
  }
  return 0;
}
inline long long gcd(long long a, long long b) {
  while (b) {
    long long c = a;
    a = b;
    b = c % b;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
bool isprime(long long n) {
  if (n == 1) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
template <typename T>
T mypow(T a, long long b) {
  T res(1);
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}
long long modpow(long long a, long long b, long long m) {
  long long res(1);
  while (b) {
    if (b & 1) {
      res *= a;
      res /= m;
    }
    a *= a;
    a /= m;
    b >>= 1;
  }
  return res;
}
template <typename T>
void printArray(std::vector<T>& vec) {
  for (int i = 0; i < (vec.size()); i++) {
    std::cout << vec[i];
    std::cout << (i == (int)vec.size() - 1 ? "\n" : " ");
  }
}
template <typename T>
void printArray(T l, T r) {
  T rprev = std::prev(r);
  for (T i = l; i != rprev; i++) {
    std::cout << *i << " ";
  }
  std::cout << *rprev << std::endl;
}
template <typename T>
class SegTree {
 protected:
  unsigned int n = 1, rank = 0;
  std::vector<T> node;
  T nodee;
  virtual T nodef(const T&, const T&) const = 0;

 public:
  SegTree(unsigned int m, T init, T nodee) : nodee(nodee) {
    while (n < m) {
      n *= 2;
      rank++;
    }
    node.resize(2 * n);
    for (unsigned int i = n; i < 2 * n; i++) node[i] = init;
  }
  SegTree(const std::vector<T>& initvec, T nodee) : nodee(nodee) {
    unsigned int m = initvec.size();
    while (n < m) {
      n *= 2;
      rank++;
    }
    node.resize(2 * n, nodee);
    for (unsigned int i = n; i < 2 * n; i++) {
      if (i - n < m) node[i] = initvec[i - n];
    }
  }
  virtual void init(const std::vector<T>& initvec) {
    n = 1;
    rank = 0;
    unsigned int m = initvec.size();
    while (n < m) {
      n *= 2;
      rank++;
    }
    node.resize(2 * n, nodee);
    for (unsigned int i = n; i < 2 * n; i++) {
      if (i - n < m) node[i] = initvec[i - n];
    }
  }
  virtual void update(int i, T x) {
    i += n;
    node[i] = x;
    while (i != 1) {
      i >>= 1;
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
    }
  }
  virtual T query(int l, int r) {
    l += n;
    r += n;
    T ls = nodee, rs = nodee;
    while (l < r) {
      if (l & 1) {
        ls = nodef(ls, node[l]);
        l++;
      }
      if (r & 1) {
        r--;
        rs = nodef(node[r], rs);
      }
      l >>= 1;
      r >>= 1;
    }
    return nodef(ls, rs);
  }
  virtual T operator[](const int& x) { return node[n + x]; }
  void print() {
    for (int i = 0; i < (n); i++) std::cout << operator[](i) << " ";
    std::cout << std::endl;
  }
};
class RSQ : public SegTree<long long> {
  long long nodef(const long long& lhs, const long long& rhs) const {
    return lhs + rhs;
  }

 public:
  RSQ(int size, const long long& def = 0) : SegTree<long long>(size, def, 0) {}
  RSQ(const std::vector<long long>& initvec) : SegTree<long long>(initvec, 0) {}
};
class RMiQ : public SegTree<long long> {
  long long nodef(const long long& lhs, const long long& rhs) const {
    return std::min(lhs, rhs);
  }

 public:
  RMiQ(int size, const long long& def = 0)
      : SegTree<long long>(size, def, LINF) {}
  RMiQ(const std::vector<long long>& initvec)
      : SegTree<long long>(initvec, LINF) {}
};
class RMaQ : public SegTree<long long> {
  long long nodef(const long long& lhs, const long long& rhs) const {
    return std::max(lhs, rhs);
  }

 public:
  RMaQ(int size, const long long& def = 0)
      : SegTree<long long>(size, def, -LINF) {}
  RMaQ(const std::vector<long long>& initvec)
      : SegTree<long long>(initvec, -LINF) {}
};
template <typename T, typename U>
class IntervalSegTree : public SegTree<T> {
 protected:
  using SegTree<T>::n;
  using SegTree<T>::rank;
  using SegTree<T>::node;
  using SegTree<T>::nodef;
  using SegTree<T>::nodee;
  std::vector<U> lazy;
  std::vector<bool> lazyflag;
  std::vector<int> width;
  virtual void lazyf(U&, const U&) = 0;
  virtual void updf(T&, const U&, const unsigned int&) = 0;
  void eval(int k) {
    for (int i = rank; i > 0; i--) {
      int nk = k >> i;
      if (lazyflag[nk]) {
        updf(node[2 * nk], lazy[nk], width[2 * nk]);
        updf(node[2 * nk + 1], lazy[nk], width[2 * nk + 1]);
        if (lazyflag[2 * nk])
          lazyf(lazy[2 * nk], lazy[nk]);
        else
          lazy[2 * nk] = lazy[nk];
        if (lazyflag[2 * nk + 1])
          lazyf(lazy[2 * nk + 1], lazy[nk]);
        else
          lazy[2 * nk + 1] = lazy[nk];
        lazyflag[2 * nk] = lazyflag[2 * nk + 1] = true;
        lazyflag[nk] = false;
      }
    }
  }

 public:
  IntervalSegTree(unsigned int m, T init, T nodee)
      : SegTree<T>(m, init, nodee) {
    lazy.resize(2 * n);
    lazyflag.resize(2 * n);
    width.resize(2 * n);
    width[1] = n;
    for (unsigned int i = 2; i < 2 * n; i++) {
      width[i] = width[i >> 1] >> 1;
    }
  }
  IntervalSegTree(T nodee, const std::vector<T>& initvec)
      : SegTree<T>(initvec, nodee) {
    lazy.resize(2 * n);
    lazyflag.resize(2 * n);
    width.resize(2 * n);
    width[1] = n;
    for (unsigned int i = 2; i < 2 * n; i++) {
      width[i] = width[i >> 1] >> 1;
    }
  }
  virtual void init(const std::vector<T>& initvec) {
    SegTree<T>::init(initvec);
    lazy.resize(2 * n);
    lazyflag.resize(2 * n, false);
    width.resize(2 * n);
    width[1] = n;
    for (unsigned int i = 2; i < 2 * n; i++) {
      width[i] = width[i >> 1] >> 1;
    }
  }
  void update(int i, U x) {
    i += n;
    eval(i);
    updf(node[i], x, width[i]);
    if (lazyflag[i])
      lazyf(lazy[i], x);
    else {
      lazyflag[i] = true;
      lazy[i] = x;
    }
    while (i /= 2) node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void update(int l, int r, U x) {
    l += n;
    r += n;
    int nl = l, nr = r;
    while (!(nl & 1)) nl >>= 1;
    while (!(nr & 1)) nr >>= 1;
    nr--;
    eval(nl);
    eval(nr);
    while (l < r) {
      if (l & 1) {
        updf(node[l], x, width[l]);
        if (lazyflag[l])
          lazyf(lazy[l], x);
        else {
          lazyflag[l] = true;
          lazy[l] = x;
        }
        l++;
      }
      if (r & 1) {
        r--;
        updf(node[r], x, width[r]);
        if (lazyflag[r])
          lazyf(lazy[r], x);
        else {
          lazyflag[r] = true;
          lazy[r] = x;
        }
      }
      l >>= 1;
      r >>= 1;
    }
    while (nl >>= 1) node[nl] = nodef(node[2 * nl], node[2 * nl + 1]);
    while (nr >>= 1) node[nr] = nodef(node[2 * nr], node[2 * nr + 1]);
  }
  T query(int l, int r) {
    l += n;
    r += n;
    eval(l);
    eval(r - 1);
    T ls = nodee, rs = nodee;
    while (l < r) {
      if (l & 1) {
        ls = nodef(ls, node[l]);
        l++;
      }
      if (r & 1) {
        r--;
        rs = nodef(node[r], rs);
      }
      l >>= 1;
      r >>= 1;
    }
    return nodef(ls, rs);
  }
  T operator[](const int& x) {
    eval(n + x);
    return node[n + x];
  }
  T queryForAll() { return node[1]; }
};
class RAQRSQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long& a, const long long& b) const {
    return a + b;
  }
  void lazyf(long long& a, const long long& b) { a += b; }
  void updf(long long& a, const long long& b, const unsigned int& width) {
    a += width * b;
  }

 public:
  RAQRSQ(int size, const long long& def = 0)
      : IntervalSegTree<long long, long long>(size, def, 0) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RAQRSQ(const std::vector<long long>& initvec)
      : IntervalSegTree<long long, long long>((long long)0, initvec) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void init(const std::vector<long long>& initvec) {
    IntervalSegTree<long long, long long>::init(initvec);
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RAQRMiQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long& a, const long long& b) const {
    return std::min(a, b);
  }
  void lazyf(long long& a, const long long& b) { a += b; }
  void updf(long long& a, const long long& b, const unsigned int& width) {
    a += b;
  }

 public:
  RAQRMiQ(int size, const long long& def = 0)
      : IntervalSegTree<long long, long long>(size, def, LINF) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RAQRMiQ(const std::vector<long long>& initvec)
      : IntervalSegTree<long long, long long>(LINF, initvec) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void init(const std::vector<long long>& initvec) {
    IntervalSegTree<long long, long long>::init(initvec);
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RAQRMaQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long& a, const long long& b) const {
    return std::max(a, b);
  }
  void lazyf(long long& a, const long long& b) { a += b; }
  void updf(long long& a, const long long& b, const unsigned int& width) {
    a += b;
  }

 public:
  RAQRMaQ(unsigned int size, const long long& def = 0)
      : IntervalSegTree<long long, long long>(size, def, -LINF) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RAQRMaQ(const std::vector<long long>& initvec)
      : IntervalSegTree<long long, long long>(-LINF, initvec) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void init(const std::vector<long long>& initvec) {
    IntervalSegTree<long long, long long>::init(initvec);
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RUQRSQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long& a, const long long& b) const {
    return a + b;
  }
  void lazyf(long long& a, const long long& b) { a = b; }
  void updf(long long& a, const long long& b, const unsigned int& width) {
    a = width * b;
  }

 public:
  RUQRSQ(int size, const int& def = 0)
      : IntervalSegTree<long long, long long>(size, def, 0) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RUQRSQ(const std::vector<long long>& initvec)
      : IntervalSegTree<long long, long long>((long long)0, initvec) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void init(const std::vector<long long>& initvec) {
    IntervalSegTree<long long, long long>::init(initvec);
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RUQRMiQ : public IntervalSegTree<long long, long long> {
  long long nodef(const int& a, const int& b) const { return std::min(a, b); }
  void lazyf(int& a, const int& b) { a = b; }
  void updf(int& a, const int& b, const unsigned int& width) { a = b; }

 public:
  RUQRMiQ(int size, const long long& def = 0)
      : IntervalSegTree<long long, long long>(size, def, LINF) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RUQRMiQ(const std::vector<long long>& initvec)
      : IntervalSegTree<long long, long long>(LINF, initvec) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void init(const std::vector<long long>& initvec) {
    IntervalSegTree<long long, long long>::init(initvec);
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RUQRMaQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long& a, const long long& b) const {
    return std::max(a, b);
  }
  void lazyf(long long& a, const long long& b) { a = b; }
  void updf(long long& a, const long long& b, const unsigned int& width) {
    a = b;
  }

 public:
  RUQRMaQ(int size, const long long& def = 0)
      : IntervalSegTree<long long, long long>(size, def, -LINF) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RUQRMaQ(const std::vector<long long>& initvec)
      : IntervalSegTree<long long, long long>(-LINF, initvec) {
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void init(const std::vector<long long>& initvec) {
    IntervalSegTree<long long, long long>::init(initvec);
    for (int i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
int n;
std::vector<long long> h, g;
int main() {
  scanf("%d", &n);
  h.resize(n);
  for (int i = 0; i < (n); i++) scanf("%d", h.data() + i);
  int min = 0, max = *std::max_element(h.begin(), h.end()) + 1;
  while (min + 1 < max) {
    int mid = (min + max) / 2;
    if (n < mid * 2 - 1) {
      max = mid;
      continue;
    }
    g = h;
    for (int i = 0; i < (mid); i++) g[i] -= i + 1;
    for (int i = mid; i < 2 * mid - 1; i++) g[i] -= 2 * mid - 1 - i;
    RAQRMiQ st(g);
    bool f = false;
    for (int i = 0; i < (n - 2 * mid + 1); i++) {
      if (st.query(i, i + 2 * mid - 1) >= 0) {
        f = true;
        break;
      }
      st.update(i, i + mid, 1);
      st.update(i + mid, i + 2 * mid, -1);
    }
    if (st.query(n - 2 * mid + 1, n) >= 0) f = true;
    if (f)
      min = mid;
    else
      max = mid;
  }
  printf("%d\n", min);
  return 0;
}
