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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

#include <ext/random>

__gnu_cxx::sfmt19937 rnd(7122);

const int inf = 1e9;

struct treap {
  int index;
  int val;
  int mn;

  int size;
  uint32_t pri;
  treap *lc, *rc, *pa;
  treap(int i) : index(i), val(i), mn(i), size(1), pri(rnd()), lc(nullptr), rc(nullptr), pa(nullptr) {}
  void pull() {
    pa = nullptr;
    size = 0;
    val = inf;
    mn = inf;
    if (lc) {
      val = min(val, lc->val);
      size += lc->size;
      mn = min(mn, lc->mn);
      lc->pa = this;
    }
    val = min(val, index - size);
    size += 1;
    mn = min(mn, index);
    if (rc) {
      val = min(val, rc->val - size * 2);
      size += rc->size;
      mn = min(mn, rc->mn);
      rc->pa = this;
    }
  }
};

int SZ(treap *x) { return x ? x->size : 0; }

treap *merge(treap *L, treap *R) {
    if (not L or not R) return L ? L : R;
    if (L->pri > R->pri)
      return L->rc = merge(L->rc, R), L->pull(), L;
    else
      return R->lc = merge(L, R->lc), R->pull(), R;
}

void splitBySize(treap *o, int k, treap *&L, treap *&R) {
  if (not o) L = R = nullptr;
  else if (int s = SZ(o->lc) + 1; s <= k)
    L = o, splitBySize(o->rc, k - s, L->rc, R), L->pull();
  else
    R = o, splitBySize(o->lc, k, L, R->lc), R->pull();
} // SZ(L) == k

void split(treap *o, int v, treap *&L, treap *&R) { // put <= v into L
  if (not o) L = R = nullptr;
  else if (o->index <= v)
    L = o, split(o->rc, v, L->rc, R), L->pull();
  else
    R = o, split(o->lc, v, L, R->lc), R->pull();
}

int getRank(treap *o) {
  int r = SZ(o->lc) + 1;
  for (; o->pa; o = o->pa)
    if (o->pa->rc == o)
      r += SZ(o->pa->lc) + 1;
  return r;
}

void dump(treap *o) {
  vector<int> to_dump;
  const auto dfs = [&](auto self, treap *p) {
    if (!p) return;
    self(self, p->lc);
    to_dump.emplace_back(p->index);
    self(self, p->rc);
  };
  dfs(dfs, o);
  orange(all(to_dump));
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> arr(n + 1);
  for (int &ai : arr)
    cin >> ai;

  vector<pair<int,int>> evt;
  for (int i = 0; i <= n; i++) {
    evt.emplace_back(arr[i], i);
  }
  ranges::sort(evt);

  // initially all 1
  vector<int> before(n + 1);
  vector<int> one_step_after(n + 1);
  for (int i = 0; i <= n; i++) {
    before[i] = 1;
  }
  one_step_after = before;

  // TODO insert into treap

  int ans = 0;
  treap *root = nullptr;
  const auto update = [&](int p, int v) {
    if (v == 0) {
      treap *A, *B, *C;
      split(root, p - 1, A, B);
      auto Z = B;
      split(Z, p, B, C);
      root = merge(A, C);
    } else {
      treap *A, *B;
      split(root, p - 1, A, B);
      assert (!B || B->mn != p);
      root = merge(merge(A, new treap(p)), B);
    }
  };

  const auto query = [&]() {
    assert (root);

    dump(root);
    debug(root->val, root->size);
    // suppose go root->size - 1 step
    if (root->val + root->size - 1 + root->size - 1 < n) {
      int res = root->size - 1 + n - (root->val + root->size - 1 + root->size - 1);
      debug(root->val + root->size - 1);
      return res;
    }

    if (root->mn + root->size - 1 == n) {
      return 0;
    }


    treap *A, *B;
    int l = 1, r = root->size;
    while (r - l > 1) {
      int m = (l + r) / 2;
      splitBySize(root, m, A, B);
      int cur_val = (A ? A->val : inf);
      root = merge(A, B);
      if (m - 1 + cur_val + root->size - 1 < n) {
        l = m;
      } else {
        r = m;
      }
    }

    return l;
  };

  for (int i = 0; i <= n; i++)
    update(i, 1);
  set<int> st;
  for (int i = 0; i <= n; i++)
    st.emplace(i);

  debug(root ? root->size : 0);

  for (auto [x, y] : evt) {
    auto cur = query() + (*st.begin() + st.size() - 1 != n);
    debug(*st.begin(), st.size());
    ans = max(ans, cur);
    debug(cur);
    // set before to 0
    before[y] = 0;
    st.erase(y);
    for (int i : {y - 1, y, y + 1}) {
      if (i < 0 || i % 2 == 1) continue;
      if (i > n) continue;
      if (i + 1 > n) {
        int &a = one_step_after[i];
        if (a != before[i])
          update(i, before[i]);
        a = before[i];
        continue;
      }
      int &a = one_step_after[i];
      int &b = one_step_after[i + 1];
      if (before[i] == 1 && before[i + 1] == 0) {
        if (a != 0)
          update(i, 0);
        if (b != 1)
          update(i + 1, 1);
        a = 0;
        b = 1;
      } else {
        if (a != before[i])
          update(i, before[i]);
        if (b != before[i + 1])
          update(i + 1, before[i + 1]);
        a = before[i];
        b = before[i + 1];
      }
    }
  }

  cout << ans << '\n';

  return 0;
}