#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;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
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;
}

```