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.
#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
const long long mod = 1000000007;
int rnd(int x) { return mrand() % x; }
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int N = 201000;
int n, a[N], p[N];
struct node {
  int mx;
} nd[8 * N];
void modify(int p, int l, int r, int tl, int x) {
  if (l == r)
    nd[p].mx = max(nd[p].mx, x);
  else {
    int md = (l + r) >> 1;
    if (tl <= md)
      modify(p + p, l, md, tl, x);
    else
      modify(p + p + 1, md + 1, r, tl, x);
    nd[p].mx = max(nd[p + p].mx, nd[p + p + 1].mx);
  }
}
int get(int p, int l, int r, int tl, int tr) {
  if (l > tr || r < tl) return 0;
  if (tl <= l && r <= tr)
    return nd[p].mx;
  else {
    int md = (l + r) >> 1;
    return max(get(p + p, l, md, tl, tr), get(p + p + 1, md + 1, r, tl, tr));
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n + 1; i++) scanf("%d", a + i), p[i] = i;
  sort(p + 1, p + n + 1, [&](int i, int j) { return i - a[i] < j - a[j]; });
  for (int i = 1; i < n + 1; i++)
    if (a[p[i]] >= 1 && a[p[i]] <= p[i]) {
      modify(1, 1, n, a[p[i]], get(1, 1, n, 1, a[p[i]] - 1) + 1);
    }
  printf("%d", nd[1].mx);
}
