#include <bits/stdc++.h>
using namespace std;
int n, ans, tmp;
vector<int> v[200005];
map<int, int> x[800005];
int f1(int a, int b, int l, int r, int i) {
  if (a == l && b == r) {
    auto it = x[i].upper_bound(tmp);
    if (it == x[i].begin()) return 0;
    it--;
    return it->second;
  }
  int mi = (l + r) / 2;
  if (b <= mi) return f1(a, b, l, mi, i * 2);
  if (a >= mi) return f1(a, b, mi, r, i * 2 + 1);
  return max(f1(a, mi, l, mi, i * 2), f1(mi, b, mi, r, i * 2 + 1));
}
void f2(int a, int b, int l, int r, int i) {
  bool g = 0;
  auto it = x[i].lower_bound(tmp);
  if (it != x[i].begin()) {
    it--;
    if (it->second >= b) g = 1;
    it++;
  }
  if (it != x[i].end() && it->first == tmp && it->second >= b) g = 1;
  if (!g) {
    auto ib = it;
    while (ib != x[i].end() && b >= ib->second) ib++;
    if (it != ib) it = x[i].erase(it, ib);
    x[i].insert(it, {tmp, b});
  }
  if (a == l && a + 1 == r) return;
  int mi = (l + r) / 2;
  if (a < mi)
    f2(a, b, l, mi, i * 2);
  else
    f2(a, b, mi, r, i * 2 + 1);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int ttmp;
    scanf("%d", &ttmp);
    v[ttmp].push_back(i);
  }
  for (int i = 1; i <= 200000; i++) {
    reverse(v[i].begin(), v[i].end());
    for (int j : v[i]) {
      if (j < i - 1) break;
      tmp = j - i + 1;
      int add = j ? f1(0, j, 0, n, 1) + 1 : 1;
      ans = max(ans, add);
      f2(j, add, 0, n, 1);
    }
  }
  printf("%d\n", ans);
}

### Prompt

Your task is to create 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;
int n, ans, tmp;
vector<int> v[200005];
map<int, int> x[800005];
int f1(int a, int b, int l, int r, int i) {
  if (a == l && b == r) {
    auto it = x[i].upper_bound(tmp);
    if (it == x[i].begin()) return 0;
    it--;
    return it->second;
  }
  int mi = (l + r) / 2;
  if (b <= mi) return f1(a, b, l, mi, i * 2);
  if (a >= mi) return f1(a, b, mi, r, i * 2 + 1);
  return max(f1(a, mi, l, mi, i * 2), f1(mi, b, mi, r, i * 2 + 1));
}
void f2(int a, int b, int l, int r, int i) {
  bool g = 0;
  auto it = x[i].lower_bound(tmp);
  if (it != x[i].begin()) {
    it--;
    if (it->second >= b) g = 1;
    it++;
  }
  if (it != x[i].end() && it->first == tmp && it->second >= b) g = 1;
  if (!g) {
    auto ib = it;
    while (ib != x[i].end() && b >= ib->second) ib++;
    if (it != ib) it = x[i].erase(it, ib);
    x[i].insert(it, {tmp, b});
  }
  if (a == l && a + 1 == r) return;
  int mi = (l + r) / 2;
  if (a < mi)
    f2(a, b, l, mi, i * 2);
  else
    f2(a, b, mi, r, i * 2 + 1);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int ttmp;
    scanf("%d", &ttmp);
    v[ttmp].push_back(i);
  }
  for (int i = 1; i <= 200000; i++) {
    reverse(v[i].begin(), v[i].end());
    for (int j : v[i]) {
      if (j < i - 1) break;
      tmp = j - i + 1;
      int add = j ? f1(0, j, 0, n, 1) + 1 : 1;
      ans = max(ans, add);
      f2(j, add, 0, n, 1);
    }
  }
  printf("%d\n", ans);
}

```