Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with n elements a1, a2, ..., an in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it G) initially has n vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode). 
    
    
      
    procedure bubbleSortGraph()  
        build a graph G with n vertices and 0 edges  
        repeat  
            swapped = false  
            for i = 1 to n - 1 inclusive do:  
                if a[i] > a[i + 1] then  
                    add an undirected edge in G between a[i] and a[i + 1]  
                    swap( a[i], a[i + 1] )  
                    swapped = true  
                end if  
            end for  
        until not swapped   
        /* repeat the algorithm as long as swapped value is true. */   
    end procedure  
    

For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph G, if we use such permutation as the premutation a in procedure bubbleSortGraph.

Input

The first line of the input contains an integer n (2 ≤ n ≤ 105). The next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n).

Output

Output a single integer — the answer to the problem. 

Examples

Input

3
3 1 2


Output

2

Note

Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].
import java.io.DataInputStream;
import java.io.InputStream;



public class D {

    public static void main (String [] args) throws Exception{
        D a= new D();
        Parserdoubt pd= a.new Parserdoubt(System.in);
        
        int n= pd.nextInt();
        int [] arr= new int[n];
        for(int i=0;i<n;i++){
            arr[i]= pd.nextInt();
        }
        
        System.out.println(a.LongestIncreasingSubsequenceLength(arr,n ));
        
        
    }
    
    
    int CeilIndex(int A[], int l, int r, int key) {
        int m;
     
        while( r - l > 1 ) {
            m = l + (r - l)/2;
          //  (A[m] >= key?r:l)=m; // ternary expression returns an l-value
            
            if(A[m]>=key)
                r=m;
            else
                l=m;
        }
     
        return r;
    }
     
    int LongestIncreasingSubsequenceLength(int A[], int size) {
        // Add boundary case, when array size is one
     
        int []tailTable   = new int[size];
        int len; // always points empty slot
     
     
     
        tailTable[0] = A[0];
        len = 1;
        for( int i = 1; i < size; i++ ) {
            if( A[i] < tailTable[0] )
                // new smallest value
                tailTable[0] = A[i];
            else if( A[i] > tailTable[len-1] )
                // A[i] wants to extend largest subsequence
                tailTable[len++] = A[i];
            else
                // A[i] wants to be current end candidate of an existing subsequence
                // It will replace ceil value in tailTable
                tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];
        }
     
       
     
        return len;
    }
    
    
    class Parserdoubt {
        final private int BUFFER_SIZE = 1 << 17;

        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Parserdoubt(InputStream in) {
            din = new DataInputStream(in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextString() throws Exception {
            StringBuffer sb = new StringBuffer("");
            byte c = read();
            while (c <= ' ')
                c = read();
            do {
                sb.append((char) c);
                c = read();
            } while (c > ' ');
            return sb.toString();
        }

        public char nextChar() throws Exception {
            byte c = read();
            while (c <= ' ')
                c = read();
            return (char) c;
        }

        public int nextInt() throws Exception {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = c == '-';
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
                c = read();
            } while (c > ' ');
            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws Exception {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = c == '-';
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
                c = read();
            } while (c > ' ');
            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws Exception {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws Exception {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
    }
    
}
