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.
// Don't place your source in a package


import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("src/text.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");
        //File file = new File("src/text.txt");

        int T=1;
        for(int t=0;t<T;t++){
            Solution sol1=new Solution(out,fs);
            sol1.solution();
        }
        out.flush();

    }


    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution {
    PrintWriter out;
    int INF = 10000000;
    int MOD = 998244353 ;
    long mod = 1000000007;
    Main.FastScanner fs;
    public Solution(PrintWriter out,Main.FastScanner fs) {
        this.out = out;
        this.fs=fs;
    }



    public void solution() {

        int n =fs.Int();
        int A[][]=new int[n][2];
        int res = 0;
        for(int i = 0; i < n;i++){
            A[i][0]=fs.Int()-1;
            A[i][1]=i;
        }

        Arrays.sort(A,(a,b)->{
            if(a[0]==b[0])return a[1]-b[1];
            return a[0]-b[0];
        });

        Seg seg = new Seg(0, 2 * n + 10);

        //A[j] + (i - j) >= A[i]
        //A[j] - j >= A[i] - i

        for(int j = 0; j < A.length;j++){
            int val = A[j][0];
            int i = A[j][1];

            int dif =  A[j][0] - i + n + 1;
            if(A[j][0] > i)continue;
            int mx = 0;
            mx = seg.query(dif, 2 * n + 5);

            res=Math.max(res,mx+1);
            seg.update(dif,mx + 1);
        }
        //System.out.println();

        out.println(res);
    }



}



class Seg{
    int l,r;
    int max=0;
    Seg left=null,right=null;
    public Seg(int l,int r){
        this.l=l;
        this.r=r;
        if(l!=r){
            int mid=l+(r-l)/2;
            if(l<=mid)left=new Seg(l,mid);
            if(r>=mid+1)right=new Seg(mid+1,r);
            if(left!=null)this.max=Math.max(max,left.max);
            if(right!=null)this.max=Math.max(max,right.max);
        }else{

        }
    }
    public int query(int s,int e){
        if(l==s&&r==e){
            return max;
        }
        int mid=l+(r-l)/2; //left :  to mid-1,
        if(e<=mid){
            return left.query(s,e);
        }
        else if(s>=mid+1){
            return right.query(s,e);
        }else{
            return Math.max(left.query(s,mid),right.query(mid+1,e));
        }
    }

    public void update(int index,int val){
        if(l==r){
            max=Math.max(max,val);
            return;
        }
        int mid=l+(r-l)/2;
        if(index<=mid){
            left.update(index,val);
        }else{
            right.update(index,val);
        }
        this.max=Math.max(left.max,right.max);
    }
}



