#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 3;
struct node {
  int a, b;
} q[maxn], t[maxn];
int cmp1(node x, node y) {
  if (x.a == y.a) return x.b < y.b;
  return x.a < y.a;
}
int n, tr[maxn], tot;
void add(int x, int y) {
  for (int i = x; i < 2e5 + 3; i += i & (-i)) {
    tr[i] = max(tr[i], y);
  }
}
int que(int x) {
  int res = 0;
  for (int i = x; i; i -= i & (-i)) {
    res = max(res, tr[i]);
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &q[i].a);
    q[i].b = i - q[i].a;
  }
  sort(q + 1, q + n + 1, cmp1);
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (q[i].a != q[i - 1].a) {
      for (int j = 1; j <= tot; ++j) add(t[j].a, t[j].b);
      tot = 0;
    }
    if (q[i].b < 0) continue;
    int res = que(q[i].b + 1);
    t[++tot].a = q[i].b + 1;
    t[tot].b = res + 1;
    ans = max(ans, res + 1);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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;
const int maxn = 2e5 + 3;
struct node {
  int a, b;
} q[maxn], t[maxn];
int cmp1(node x, node y) {
  if (x.a == y.a) return x.b < y.b;
  return x.a < y.a;
}
int n, tr[maxn], tot;
void add(int x, int y) {
  for (int i = x; i < 2e5 + 3; i += i & (-i)) {
    tr[i] = max(tr[i], y);
  }
}
int que(int x) {
  int res = 0;
  for (int i = x; i; i -= i & (-i)) {
    res = max(res, tr[i]);
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &q[i].a);
    q[i].b = i - q[i].a;
  }
  sort(q + 1, q + n + 1, cmp1);
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (q[i].a != q[i - 1].a) {
      for (int j = 1; j <= tot; ++j) add(t[j].a, t[j].b);
      tot = 0;
    }
    if (q[i].b < 0) continue;
    int res = que(q[i].b + 1);
    t[++tot].a = q[i].b + 1;
    t[tot].b = res + 1;
    ans = max(ans, res + 1);
  }
  cout << ans << endl;
  return 0;
}

```