description: 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.
solution: #include <bits/stdc++.h>
  using namespace std;
  const int MAXN = 2e5 + 10;
  int n;
  int a[MAXN];
  struct pt {
    int dest, offset, pos, ans;
  } pts[MAXN], tmp[MAXN];
  bool cmp_dest(const pt &a, const pt &b) { return a.dest < b.dest; }
  bool cmp_offset(const pt &a, const pt &b) { return a.offset < b.offset; }
  bool cmp_pos(const pt &a, const pt &b) { return a.pos < b.pos; }
  inline int lowbit(int x) { return x & (-x); }
  int tree[MAXN];
  void add(int x, int p) {
    p++;
    while (p < MAXN) {
      tree[p] = max(tree[p], x);
      p += lowbit(p);
    }
  }
  void rem(int p) {
    p++;
    while (p < MAXN) {
      tree[p] = 0;
      p += lowbit(p);
    }
  }
  int query(int p) {
    int ret = 0;
    p++;
    while (p > 0) {
      ret = max(ret, tree[p]);
      p -= lowbit(p);
    }
    return ret;
  }
  void cdq(int l, int r) {
    if (l + 1 == r) return;
    int mid = (l + r) / 2;
    sort(pts + l, pts + mid, cmp_pos);
    cdq(l, mid);
    sort(pts + l, pts + mid, cmp_dest);
    sort(pts + mid, pts + r, cmp_dest);
    int ll = l;
    for (int i = mid; i < r; i++) {
      while (ll < mid && pts[ll].dest < pts[i].dest) {
        if (pts[ll].offset >= 0) add(pts[ll].ans, pts[ll].offset);
        ll++;
      }
      if (pts[i].offset >= 0)
        pts[i].ans = max(pts[i].ans, query(pts[i].offset) + 1);
    }
    for (int i = l; i < ll; i++)
      if (pts[i].offset >= 0) rem(pts[i].offset);
    sort(pts + mid, pts + r, cmp_pos);
    cdq(mid, r);
  }
  int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &pts[i].dest);
      pts[i].offset = i - pts[i].dest;
      pts[i].pos = i;
      if (pts[i].offset >= 0) pts[i].ans = 1;
    }
    cdq(1, n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
      if (pts[i].ans > ans) ans = pts[i].ans;
    printf("%d", ans);
    return 0;
  }
  