#include <bits/stdc++.h>
using namespace std;
int const N = 2e5 + 123;
vector<int> ST(4 * N, 0);
void update(int k, int l, int r, int idx, int val) {
  if (l > idx || r < idx) return;
  if (l == r && l == idx) {
    ST[k] = val;
    return;
  }
  int m = (l + r) >> 1;
  update(k << 1, l, m, idx, val);
  update(k << 1 | 1, m + 1, r, idx, val);
  ST[k] = max(ST[k << 1], ST[k << 1 | 1]);
}
int getLis(int k, int l, int r, int from, int to) {
  if (l > r) return 0;
  if (l > to || from > r) return 0;
  if (from <= l && r <= to) return ST[k];
  int m = (l + r) >> 1;
  return max(getLis(k << 1, l, m, from, to),
             getLis(k << 1 | 1, m + 1, r, from, to));
}
void TestCase() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto& x : v) cin >> x;
  vector<pair<int, int>> p;
  for (int i = 0; i < n; i++) {
    if (i - v[i] + 1 >= 0) {
      p.push_back({i - v[i] + 1, v[i]});
    }
  }
  sort(p.begin(), p.end());
  vector<int> LIS(2 * N + 5, 0);
  int answer = 0;
  for (int i = 0; i < p.size(); i++) {
    LIS[p[i].second] = getLis(1, 0, n, 0, p[i].second - 1) + 1;
    update(1, 0, n, p[i].second, LIS[p[i].second]);
    answer = max(answer, LIS[p[i].second]);
  }
  cout << answer << '\n';
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int T = 1;
  while (T--) {
    TestCase();
  }
}

### Prompt

Your challenge is to write 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 const N = 2e5 + 123;
vector<int> ST(4 * N, 0);
void update(int k, int l, int r, int idx, int val) {
  if (l > idx || r < idx) return;
  if (l == r && l == idx) {
    ST[k] = val;
    return;
  }
  int m = (l + r) >> 1;
  update(k << 1, l, m, idx, val);
  update(k << 1 | 1, m + 1, r, idx, val);
  ST[k] = max(ST[k << 1], ST[k << 1 | 1]);
}
int getLis(int k, int l, int r, int from, int to) {
  if (l > r) return 0;
  if (l > to || from > r) return 0;
  if (from <= l && r <= to) return ST[k];
  int m = (l + r) >> 1;
  return max(getLis(k << 1, l, m, from, to),
             getLis(k << 1 | 1, m + 1, r, from, to));
}
void TestCase() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto& x : v) cin >> x;
  vector<pair<int, int>> p;
  for (int i = 0; i < n; i++) {
    if (i - v[i] + 1 >= 0) {
      p.push_back({i - v[i] + 1, v[i]});
    }
  }
  sort(p.begin(), p.end());
  vector<int> LIS(2 * N + 5, 0);
  int answer = 0;
  for (int i = 0; i < p.size(); i++) {
    LIS[p[i].second] = getLis(1, 0, n, 0, p[i].second - 1) + 1;
    update(1, 0, n, p[i].second, LIS[p[i].second]);
    answer = max(answer, LIS[p[i].second]);
  }
  cout << answer << '\n';
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int T = 1;
  while (T--) {
    TestCase();
  }
}

```