/*
 * _|_|_|_|_|  _|_|_|_|    _|_|_|  _|_|_|_|_|  _|_|_|      _|_|
 *       _|    _|        _|                _|        _|  _|    _|
 *     _|      _|_|_|      _|_|          _|      _|_|        _|
 *   _|        _|              _|      _|            _|    _|
 * _|_|_|_|_|  _|        _|_|_|      _|        _|_|_|    _|_|_|_|
 */

#include <bits/stdc++.h>

int main() 
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N;
  std::cin >> N;
  std::vector<int> A(N);
  for (auto &v: A) { std::cin >> v; }

  auto Check = [&](int lim) -> bool {
    int l1{}, r1{}, l2{}, r2{}, tr{1}, cnt{};

    auto All = [&](int all) {
      int ret = all;
      if (cnt >= 1) { ret += std::clamp(all - l1, 0, r1 - l1); }
      if (cnt >= 2) { ret += std::clamp(all - l2, 0, r2 - l2); }
      return ret;
    };

    auto Get = [&](int all) {
      if (cnt == 0 || all <= l1) { return all; }
      all -= l1;
      if (all <= 2 * (r1 - l1)) { return l1 + (all + 1) / 2; }
      all -= 2 * (r1 - l1);
      if (cnt == 1 || all <= l2 - r1) { return r1 + all; }
      all -= l2 - r1;
      if (all <= 2 * (r2 - l2)) { return l2 + (all + 1) / 2; }
      all -= 2 * (r2 - l2);
      return r2 + all;
    };

    for (int i = 0; i < N; i++) {
      if (tr == 1 || !cnt) {
        int ti = Get(A[i]);
        if (ti > lim) {
          int rem = A[i] - All(lim);
          l1 = lim - rem, r1 = lim;
          tr = -1, cnt = 1;
        } else {
          l1 = ti, r1 = lim;
          tr = 1, cnt = 1;
        }
      } else {
        assert(cnt == 1);
        int ti = Get(A[i]);
        if (ti > l1) {
          int rem = A[i] - All(l1);
          r1 = l1, l1 = l1 - rem;
          tr = -1, cnt = 1;
        } else {
          l2 = r1, r2 = lim;
          r1 = l1, l1 = ti;
          tr = 1, cnt = 2;
        }
      }
      if (l1 < -1) { return false; }
    }
    return ~tr;
  };

  int L = *std::ranges::min_element(A);
  int R = *std::ranges::max_element(A);
  while (L < R) {
    int M = (L + R) >> 1;
    if (Check(M)) {
      R = M;
    } else {
      L = M + 1;
    }
  }
  std::cout << L << '\n';

  return 0;
}

answer.code:12:3: error: expected initializer before ‘std’
   12 |   std::ios::sync_with_stdio(false);
      |   ^~~
answer.code:13:8: error: ‘cin’ in namespace ‘std’ does not name a type
   13 |   std::cin.tie(nullptr);
      |        ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:146,
                 from answer.code:9:
/usr/include/c++/14/iostream:62:18: note: ‘std::cin’ declared here
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
answer.code:16:8: error: ‘cin’ in namespace ‘std’ does not name a type
   16 |   std::cin >> N;
      |        ^~~
/usr/include/c++/14/iostream:62:18: note: ‘std::cin’ declared here
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
answer.code:18:3: error: expected unqualified-id before ‘for’
   18 |   for (auto &v: A) { std::cin >> v; }
      |   ^~~
answer.code:20:17: error: non-local lambda expression cannot have a capture-default
   20 |   auto Check = [&](int lim) -> bool {
      |                 ^
answer.code:73:3: error: expected unqualified-id before ‘while’
   73 |   while (L < R) {
      |   ^~~~~
answer.code:81:8: error: ‘cout’ in namespace ‘std’ does not name a type
   81 |   std::cout << L << '\n';
      |        ^~~~
/usr/include/c++/14/iostream:63:18: note: ‘std::cout’ declared here
   63 |   extern ostream cout;          ///< Linked to standard output
      |                  ^~~~
answer.code:83:3: error: expected unqualified-id before ‘return’
   83 |   return 0;
      |   ^~~~~~
answer.code:84:1: error: expected declaration before ‘}’ token
   84 | }
      | ^