#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
int h[200010];

struct Nod { int l = 0, r = 0; inline int len() { return r - l; } };

inline bool chk(int mid) {
  Nod a, b;
  int l, r, p = 0;
  for (int i = 1; i <= n; i++) {
    Nod c, d;
    if (p == 0) {
      int w = mid + a.len() + b.len();
      if (w < h[i]) {
        l = mid - h[i] - w, r = mid, p = 1;
      } else {
        p = 0;
        if ((w = a.r + a.len() + b.len()) < h[i]) {
          c.l = h[i] - w + a.r, c.r = mid;
        } else if ((w = a.l + b.len()) < h[i]) {
          c.l = ((h[i] - w - 1) >> 1) + 1 + a.l, c.r = mid;
        } else if ((w = b.r + b.len()) < h[i]) {
          c.l = h[i] - w + b.r, c.r = mid;
        } else if ((w = b.l) < h[i]) {
          c.l = ((h[i] - w - 1) >> 1) + 1 + b.l, c.r = mid;
        } else {
          c.l = h[i], c.r = mid;
        }
      }
    } else {
      if (l < 0 || r > mid) return 0;
      if (a.l >= l) a = b, b.l = b.r = 0; else if (a.r >= l) a.r = l;
      if (a.l >= l) a = b, b.l = b.r = 0; else if (a.r >= l) a.r = l;
      int w = l + a.len() + b.len();
      if (w < h[i]) {
        l = (r = l) - h[i] - w, p = 1;
      } else {
        p = 0;
        if ((w = a.r + a.len() + b.len()) < h[i]) {
          d.l = h[i] - w + a.r, d.r = l;
        } else if ((w = a.l + b.len()) < h[i]) {
          d.l = ((h[i] - w - 1) >> 1) + 1 + a.l, d.r = l;
        } else if ((w = b.r + b.len()) < h[i]) {
          d.l = h[i] - w + b.r, d.r = l;
        } else if ((w = b.l) < h[i]) {
          d.l = ((h[i] - w - 1) >> 1) + 1 + b.l, d.r = l;
        } else {
          d.l = h[i], d.r = l;
        }
      }
      if (r < mid) c.l = r, c.r = mid; else swap(c, d);
    }
    a = c, b = d;
  }
  return p == 0;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  int l = 0;
  int r = 0, ns;
  for (int i = 1; i <= n; i++) cin >> h[i], r = max(r, h[i]);
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (chk(mid)) {
      r = mid - 1, ns = mid;
    } else {
      l = mid + 1;
    }
  }
  cout << ns << "\n";
}