#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
template <typename T>
bool chmax(T &x, const T &y) {
  return (x < y) ? (x = y, true) : false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  return (x > y) ? (x = y, true) : false;
}
template <typename T>
int flg(T x, int i) {
  return (x >> i) & 1;
}
template <typename T>
void print(const vector<T> &v, T x = 0) {
  int n = v.size();
  for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
}
template <typename T>
void printn(const vector<T> &v, T x = 0) {
  int n = v.size();
  for (int i = 0; i < n; i++) cout << v[i] + x << '\n';
}
template <typename T>
int lb(const vector<T> &v, T x) {
  return lower_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, T x) {
  return upper_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
void rearrange(vector<T> &v) {
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
}
template <typename T>
vector<int> id_sort(const vector<T> &v, bool greater = false) {
  int n = v.size();
  vector<int> ret(n);
  iota(begin(ret), end(ret), 0);
  sort(begin(ret), end(ret),
       [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });
  return ret;
}
struct io_setup {
  io_setup() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);
  }
} io_setup;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
const int MOD = 1000000007;
template <typename Monoid>
struct Segment_Tree {
  using F = function<Monoid(Monoid, Monoid)>;
  int n;
  vector<Monoid> seg;
  const F f;
  const Monoid e1;
  Segment_Tree(const vector<Monoid> &v, const F &f, const Monoid &e1)
      : f(f), e1(e1) {
    int m = v.size();
    n = 1;
    while (n < m) n <<= 1;
    seg.assign(2 * n, e1);
    copy(begin(v), end(v), begin(seg) + n);
    for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
  }
  Segment_Tree(int m, const Monoid &x, const F &f, const Monoid &e1)
      : f(f), e1(e1) {
    n = 1;
    while (n < m) n <<= 1;
    seg.assign(2 * n, e1);
    vector<Monoid> v(m, x);
    copy(begin(v), end(v), begin(seg) + n);
    for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
  }
  void change(int i, const Monoid &x, bool update = true) {
    if (update)
      seg[i + n] = x;
    else
      seg[i + n] = f(seg[i + n], x);
    i += n;
    while (i >>= 1) {
      seg[i] = f(seg[2 * i], seg[2 * i + 1]);
    }
  }
  Monoid query(int l, int r) const {
    Monoid L = e1, R = e1;
    l += n, r += n;
    while (l < r) {
      if (l & 1) L = f(L, seg[l++]);
      if (r & 1) R = f(seg[--r], R);
      l >>= 1, r >>= 1;
    }
    return f(L, R);
  }
  Monoid operator[](int i) const { return seg[n + i]; }
  template <typename C>
  int find_subtree(int i, const C &check, const Monoid &x, Monoid &M,
                   bool type) const {
    while (i < n) {
      Monoid nxt = type ? f(seg[2 * i + type], M) : f(M, seg[2 * i + type]);
      if (check(nxt, x))
        i = 2 * i + type;
      else
        M = nxt, i = 2 * i + (type ^ 1);
    }
    return i - n;
  }
  template <typename C>
  int find_first(int l, const C &check, const Monoid &x) const {
    Monoid L = e1;
    int a = l + n, b = n + n;
    while (a < b) {
      if (a & 1) {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt, x)) return find_subtree(a, check, x, L, false);
        L = nxt, a++;
      }
      a >>= 1, b >>= 1;
    }
    return n;
  }
  template <typename C>
  int find_last(int r, const C &check, const Monoid &x) const {
    Monoid R = e1;
    int a = n, b = r + n;
    while (a < b) {
      if (b & 1 || a == 1) {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt, x)) return find_subtree(b, check, x, R, true);
        R = nxt;
      }
      a >>= 1, b >>= 1;
    }
    return -1;
  }
};
template <typename T>
struct Segment_Tree_2D {
  using F = function<T(T, T)>;
  int n;
  vector<vector<int>> ids;
  vector<Segment_Tree<T>> segs;
  const F f;
  const T e1;
  Segment_Tree_2D(int m, const F &f, const T &e1) : f(f), e1(e1) {
    n = 1;
    while (n < m) n <<= 1;
    ids.resize(2 * n);
  }
  void insert(int x, int y) {
    x += n;
    while (x) {
      ids[x].push_back(y);
      x >>= 1;
    }
  }
  void build() {
    for (int i = 0; i < 2 * n; i++) {
      sort(begin(ids[i]), end(ids[i]));
      ids[i].erase(unique(begin(ids[i]), end(ids[i])), end(ids[i]));
      segs.emplace_back((int)ids[i].size(), e1, f, e1);
    }
  }
  void change(int x, int y, const T &a) {
    x += n;
    while (x) {
      segs[x].change(lower_bound(begin(ids[x]), end(ids[x]), y) - begin(ids[x]),
                     a, false);
      x >>= 1;
    }
  }
  T query(int lx, int rx, int ly, int ry) const {
    T L = e1, R = e1;
    lx += n, rx += n;
    while (lx < rx) {
      if (lx & 1) {
        int l = lower_bound(begin(ids[lx]), end(ids[lx]), ly) - begin(ids[lx]);
        int r = lower_bound(begin(ids[lx]), end(ids[lx]), ry) - begin(ids[lx]);
        L = f(L, segs[lx].query(l, r));
        lx++;
      }
      if (rx & 1) {
        rx--;
        int l = lower_bound(begin(ids[rx]), end(ids[rx]), ly) - begin(ids[rx]);
        int r = lower_bound(begin(ids[rx]), end(ids[rx]), ry) - begin(ids[rx]);
        R = f(segs[rx].query(l, r), R);
      }
      lx >>= 1, rx >>= 1;
    }
    return f(L, R);
  }
};
int main() {
  int N;
  cin >> N;
  vector<int> a(N + 1);
  a[0] = 0;
  for (int i = 1; i <= N; i++) cin >> a[i];
  for (int i = 0; i < N + 1; i++) a[i] += N - i;
  vector<int> xs, ys;
  for (int i = 0; i < N + 1; i++)
    xs.emplace_back(-a[i]), ys.emplace_back(a[i] + i);
  rearrange(xs), rearrange(ys);
  int K = (int)xs.size();
  auto f = [](int a, int b) { return max(a, b); };
  Segment_Tree_2D<int> seg(K, f, -inf);
  for (int i = 0; i < N + 1; i++) seg.insert(lb(xs, -a[i]), lb(ys, a[i] + i));
  seg.build();
  seg.change(lb(xs, -a[0]), lb(ys, a[0] + 0), 0);
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    int x = seg.query(0, lb(xs, -a[i] + 1), 0, lb(ys, a[i] + i)) + 1;
    seg.change(lb(xs, -a[i]), lb(ys, a[i] + i), x);
    chmax(ans, x);
  }
  cout << ans << '\n';
}

### Prompt

In cpp, your task is to solve the following problem:

Mr. Chanek gives you a sequence a indexed from 1 to n. Define f(a) as the number of indices where a_i = i. 

You can pick an element from the current sequence and remove it, then concatenate the remaining elements together. For example, if you remove the 3-rd element from the sequence [4, 2, 3, 1], the resulting sequence will be [4, 2, 1]. 

You want to remove some elements from a in order to maximize f(a), using zero or more operations. Find the largest possible f(a).

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the initial length of the sequence.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — the initial sequence a.

Output

Output an integer denoting the largest f(a) that can be obtained by doing zero or more operations.

Examples

Input


7
2 1 4 2 5 3 7


Output


3


Input


4
4 2 3 1


Output


2

Note

In the first example, f(A) = 3 by doing the following operations.

[2,1,4,2,5,3,7] → [2,1,2,5,3,7] → [1,2,5,3,7] → [1,2,5,3] → [1,2,3]

In the second example, f(A) = 2 and no additional operation is needed.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
template <typename T>
bool chmax(T &x, const T &y) {
  return (x < y) ? (x = y, true) : false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  return (x > y) ? (x = y, true) : false;
}
template <typename T>
int flg(T x, int i) {
  return (x >> i) & 1;
}
template <typename T>
void print(const vector<T> &v, T x = 0) {
  int n = v.size();
  for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
}
template <typename T>
void printn(const vector<T> &v, T x = 0) {
  int n = v.size();
  for (int i = 0; i < n; i++) cout << v[i] + x << '\n';
}
template <typename T>
int lb(const vector<T> &v, T x) {
  return lower_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, T x) {
  return upper_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
void rearrange(vector<T> &v) {
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
}
template <typename T>
vector<int> id_sort(const vector<T> &v, bool greater = false) {
  int n = v.size();
  vector<int> ret(n);
  iota(begin(ret), end(ret), 0);
  sort(begin(ret), end(ret),
       [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });
  return ret;
}
struct io_setup {
  io_setup() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);
  }
} io_setup;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
const int MOD = 1000000007;
template <typename Monoid>
struct Segment_Tree {
  using F = function<Monoid(Monoid, Monoid)>;
  int n;
  vector<Monoid> seg;
  const F f;
  const Monoid e1;
  Segment_Tree(const vector<Monoid> &v, const F &f, const Monoid &e1)
      : f(f), e1(e1) {
    int m = v.size();
    n = 1;
    while (n < m) n <<= 1;
    seg.assign(2 * n, e1);
    copy(begin(v), end(v), begin(seg) + n);
    for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
  }
  Segment_Tree(int m, const Monoid &x, const F &f, const Monoid &e1)
      : f(f), e1(e1) {
    n = 1;
    while (n < m) n <<= 1;
    seg.assign(2 * n, e1);
    vector<Monoid> v(m, x);
    copy(begin(v), end(v), begin(seg) + n);
    for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
  }
  void change(int i, const Monoid &x, bool update = true) {
    if (update)
      seg[i + n] = x;
    else
      seg[i + n] = f(seg[i + n], x);
    i += n;
    while (i >>= 1) {
      seg[i] = f(seg[2 * i], seg[2 * i + 1]);
    }
  }
  Monoid query(int l, int r) const {
    Monoid L = e1, R = e1;
    l += n, r += n;
    while (l < r) {
      if (l & 1) L = f(L, seg[l++]);
      if (r & 1) R = f(seg[--r], R);
      l >>= 1, r >>= 1;
    }
    return f(L, R);
  }
  Monoid operator[](int i) const { return seg[n + i]; }
  template <typename C>
  int find_subtree(int i, const C &check, const Monoid &x, Monoid &M,
                   bool type) const {
    while (i < n) {
      Monoid nxt = type ? f(seg[2 * i + type], M) : f(M, seg[2 * i + type]);
      if (check(nxt, x))
        i = 2 * i + type;
      else
        M = nxt, i = 2 * i + (type ^ 1);
    }
    return i - n;
  }
  template <typename C>
  int find_first(int l, const C &check, const Monoid &x) const {
    Monoid L = e1;
    int a = l + n, b = n + n;
    while (a < b) {
      if (a & 1) {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt, x)) return find_subtree(a, check, x, L, false);
        L = nxt, a++;
      }
      a >>= 1, b >>= 1;
    }
    return n;
  }
  template <typename C>
  int find_last(int r, const C &check, const Monoid &x) const {
    Monoid R = e1;
    int a = n, b = r + n;
    while (a < b) {
      if (b & 1 || a == 1) {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt, x)) return find_subtree(b, check, x, R, true);
        R = nxt;
      }
      a >>= 1, b >>= 1;
    }
    return -1;
  }
};
template <typename T>
struct Segment_Tree_2D {
  using F = function<T(T, T)>;
  int n;
  vector<vector<int>> ids;
  vector<Segment_Tree<T>> segs;
  const F f;
  const T e1;
  Segment_Tree_2D(int m, const F &f, const T &e1) : f(f), e1(e1) {
    n = 1;
    while (n < m) n <<= 1;
    ids.resize(2 * n);
  }
  void insert(int x, int y) {
    x += n;
    while (x) {
      ids[x].push_back(y);
      x >>= 1;
    }
  }
  void build() {
    for (int i = 0; i < 2 * n; i++) {
      sort(begin(ids[i]), end(ids[i]));
      ids[i].erase(unique(begin(ids[i]), end(ids[i])), end(ids[i]));
      segs.emplace_back((int)ids[i].size(), e1, f, e1);
    }
  }
  void change(int x, int y, const T &a) {
    x += n;
    while (x) {
      segs[x].change(lower_bound(begin(ids[x]), end(ids[x]), y) - begin(ids[x]),
                     a, false);
      x >>= 1;
    }
  }
  T query(int lx, int rx, int ly, int ry) const {
    T L = e1, R = e1;
    lx += n, rx += n;
    while (lx < rx) {
      if (lx & 1) {
        int l = lower_bound(begin(ids[lx]), end(ids[lx]), ly) - begin(ids[lx]);
        int r = lower_bound(begin(ids[lx]), end(ids[lx]), ry) - begin(ids[lx]);
        L = f(L, segs[lx].query(l, r));
        lx++;
      }
      if (rx & 1) {
        rx--;
        int l = lower_bound(begin(ids[rx]), end(ids[rx]), ly) - begin(ids[rx]);
        int r = lower_bound(begin(ids[rx]), end(ids[rx]), ry) - begin(ids[rx]);
        R = f(segs[rx].query(l, r), R);
      }
      lx >>= 1, rx >>= 1;
    }
    return f(L, R);
  }
};
int main() {
  int N;
  cin >> N;
  vector<int> a(N + 1);
  a[0] = 0;
  for (int i = 1; i <= N; i++) cin >> a[i];
  for (int i = 0; i < N + 1; i++) a[i] += N - i;
  vector<int> xs, ys;
  for (int i = 0; i < N + 1; i++)
    xs.emplace_back(-a[i]), ys.emplace_back(a[i] + i);
  rearrange(xs), rearrange(ys);
  int K = (int)xs.size();
  auto f = [](int a, int b) { return max(a, b); };
  Segment_Tree_2D<int> seg(K, f, -inf);
  for (int i = 0; i < N + 1; i++) seg.insert(lb(xs, -a[i]), lb(ys, a[i] + i));
  seg.build();
  seg.change(lb(xs, -a[0]), lb(ys, a[0] + 0), 0);
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    int x = seg.query(0, lb(xs, -a[i] + 1), 0, lb(ys, a[i] + i)) + 1;
    seg.change(lb(xs, -a[i]), lb(ys, a[i] + i), x);
    chmax(ans, x);
  }
  cout << ans << '\n';
}

```