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>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;

struct BIT
{
    int bit[mxn] = {};

    void update(int p,int v) {
        if(p==0) return;
        for(;p<mxn;p+=p&-p) bit[p]=max(bit[p],v);
    }
    int query(int p) {
        int r=0;
        for(;p>0;p-=p&-p) r=max(r,bit[p]);
        return r;
    }
} bt;
int main() {
    int n;
    cin >> n;
    int a[n + 1];


    vector<pii> v;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(i - a[i] >= 0) v.emplace_back(i - a[i], a[i]);
    }

    if(v.empty()) {
        cout<<0<<endl;
        return 0;
    }



    sort(v.begin(), v.end());


    int dp[n + 1] = {};

    dp[0] = 1;
    bt.update(v[0].s, 1);
    int ans = 0;


    for(int i = 1; i < v.size(); i++) {

        dp[i] = bt.query(v[i].s - 1) + 1;
        ans = max(ans, dp[i]);
        bt.update(v[i].s, dp[i]);

    }

    
    cout<<ans<<endl;
    
}