#include <bits/stdc++.h>
using namespace std;
inline int gi() {
  char tmp = getchar();
  int ans = 0, flag = 1;
  while (!isdigit(tmp)) {
    if (tmp == '-') flag = -1;
    tmp = getchar();
  }
  while (isdigit(tmp)) {
    ans = ans * 10 + tmp - '0';
    tmp = getchar();
  }
  return ans * flag;
}
inline void in(int &x) { x = gi(); }
inline void in2(int &x, int &y) { in(x), in(y); }
inline void in3(int &x, int &y, int &z) { in(x), in(y), in(z); }
inline void in4(int &x, int &y, int &z, int &a) { in3(x, y, z), in(a); }
inline void smax(int &x, int y) { x = max(x, y); }
inline void smin(int &x, int y) { x = min(x, y); }
int lowbit(int x) { return x & -x; }
const int N = 1002000;
int C[N], n, maxx;
void Add(int x, int v) {
  while (x <= maxx) {
    smax(C[x], v);
    x += lowbit(x);
  }
}
int Query(int x) {
  int ans = 0;
  while (x) {
    smax(ans, C[x]);
    x -= lowbit(x);
  }
  return ans;
}
struct Nod {
  int x, y;
} Node[N];
bool cmp(Nod a, Nod b) {
  if (a.y != b.y) return a.y < b.y;
  return a.x < b.x;
}
signed main() {
  int n = gi();
  for (int i = (int)(1); i <= (int)(n); ++i) {
    Node[i].x = gi();
    Node[i].y = i - Node[i].x;
    smax(maxx, Node[i].x);
  }
  sort(Node + 1, Node + n + 1, cmp);
  int ans = 0;
  for (int i = (int)(1); i <= (int)(n); ++i) {
    if (Node[i].y < 0) continue;
    int g = Query(Node[i].x - 1);
    Add(Node[i].x, g + 1);
    smax(ans, g + 1);
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
inline int gi() {
  char tmp = getchar();
  int ans = 0, flag = 1;
  while (!isdigit(tmp)) {
    if (tmp == '-') flag = -1;
    tmp = getchar();
  }
  while (isdigit(tmp)) {
    ans = ans * 10 + tmp - '0';
    tmp = getchar();
  }
  return ans * flag;
}
inline void in(int &x) { x = gi(); }
inline void in2(int &x, int &y) { in(x), in(y); }
inline void in3(int &x, int &y, int &z) { in(x), in(y), in(z); }
inline void in4(int &x, int &y, int &z, int &a) { in3(x, y, z), in(a); }
inline void smax(int &x, int y) { x = max(x, y); }
inline void smin(int &x, int y) { x = min(x, y); }
int lowbit(int x) { return x & -x; }
const int N = 1002000;
int C[N], n, maxx;
void Add(int x, int v) {
  while (x <= maxx) {
    smax(C[x], v);
    x += lowbit(x);
  }
}
int Query(int x) {
  int ans = 0;
  while (x) {
    smax(ans, C[x]);
    x -= lowbit(x);
  }
  return ans;
}
struct Nod {
  int x, y;
} Node[N];
bool cmp(Nod a, Nod b) {
  if (a.y != b.y) return a.y < b.y;
  return a.x < b.x;
}
signed main() {
  int n = gi();
  for (int i = (int)(1); i <= (int)(n); ++i) {
    Node[i].x = gi();
    Node[i].y = i - Node[i].x;
    smax(maxx, Node[i].x);
  }
  sort(Node + 1, Node + n + 1, cmp);
  int ans = 0;
  for (int i = (int)(1); i <= (int)(n); ++i) {
    if (Node[i].y < 0) continue;
    int g = Query(Node[i].x - 1);
    Add(Node[i].x, g + 1);
    smax(ans, g + 1);
  }
  printf("%d\n", ans);
  return 0;
}

```