#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int k = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    k = k * 10 + ch - '0';
    ch = getchar();
  }
  return k * f;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(int x) {
  write(x);
  puts("");
}
const int N = 4e5 + 10, M = 2e5;
int n;
int a[N], cntt = 0;
int f[N], maxx = 0;
struct ppap {
  int x, v;
} b[N];
inline bool cmp(ppap a, ppap b) { return a.v == b.v ? a.x > b.x : a.v < b.v; }
inline void update(int x, int v) {
  for (; x <= M + n; x += x & -x) f[x] = max(f[x], v);
}
inline int smax(int x) {
  int ans = -1;
  for (; x; x -= x & -x) {
    ans = max(ans, f[x]);
  }
  return ans;
}
int main() {
  n = read();
  memset(f, -1, sizeof f);
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    b[i] = (ppap){i, a[i]};
    maxx = max(maxx, a[i]);
  }
  sort(b + 1, b + n + 1, cmp);
  update(0 + M, 0);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int x = b[i].x, y = b[i].v;
    int p = x - y;
    int v = smax(p + M) + 1;
    if (v == 0 && p < 0) v = -1;
    ans = max(ans, v);
    update(p + M, v);
  }
  writeln(ans);
  return 0;
}

### Prompt

Please create a solution in CPP 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;
inline int read() {
  int k = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    k = k * 10 + ch - '0';
    ch = getchar();
  }
  return k * f;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(int x) {
  write(x);
  puts("");
}
const int N = 4e5 + 10, M = 2e5;
int n;
int a[N], cntt = 0;
int f[N], maxx = 0;
struct ppap {
  int x, v;
} b[N];
inline bool cmp(ppap a, ppap b) { return a.v == b.v ? a.x > b.x : a.v < b.v; }
inline void update(int x, int v) {
  for (; x <= M + n; x += x & -x) f[x] = max(f[x], v);
}
inline int smax(int x) {
  int ans = -1;
  for (; x; x -= x & -x) {
    ans = max(ans, f[x]);
  }
  return ans;
}
int main() {
  n = read();
  memset(f, -1, sizeof f);
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    b[i] = (ppap){i, a[i]};
    maxx = max(maxx, a[i]);
  }
  sort(b + 1, b + n + 1, cmp);
  update(0 + M, 0);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int x = b[i].x, y = b[i].v;
    int p = x - y;
    int v = smax(p + M) + 1;
    if (v == 0 && p < 0) v = -1;
    ans = max(ans, v);
    update(p + M, v);
  }
  writeln(ans);
  return 0;
}

```