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.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author karan173
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskD {
    public void solve(int testNumber, FastReader in, PrintWriter out) {
        int n = in.nextInt ();
        int a[] = new int[n];
        ArrayUtils.readIntArray (a, in);
        out.println (LIS.lisLength (a));
    }
}

class FastReader
{

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream)
    {
        this.stream = stream;
    }

    public int read()
    {
        if (numChars == -1)
        {
            throw new InputMismatchException ();
        }
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read (buf);
            } catch (IOException e)
            {
                throw new InputMismatchException ();
            }
            if (numChars <= 0)
            {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int nextInt()
    {
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read ();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
            {
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        } while (!isSpaceChar (c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c)
    {
        if (filter != null)
        {
            return filter.isSpaceChar (c);
        }
        return isWhitespace (c);
    }

    public static boolean isWhitespace(int c)
    {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}

class ArrayUtils
{


    public static void readIntArray(int a[], FastReader in)
    {
        for (int i = 0; i < a.length; i++)
        {
            a[i] = in.nextInt ();
        }
    }

}

class LIS
{
    public static int lisLength(int a[])
    {
        int n = a.length;
        int lowest[] = new int[n + 1];
        Arrays.fill (lowest, Integer.MAX_VALUE);
        lowest[1] = a[0];
        int maxLisLength = 1;
        for (int i = 1; i < n; i++)
        {
            //find largest j such that lowest[j] < a[i]
            //lowest[j] is also sorted since lowest[j] will be appended to a subsequence of length j-1
            //say ending at k and therefore k<lowest[j]
            //and lowest[j-1]<=k, hence lowest[j-1] <=k < lowest[j]
            //hence lowest[j-1]<lowest[j]
            //hence we can binary search over lowest[j] to find max. predecessor of a[i]
            int j = findMaxPredecessor (lowest, 1, n , a[i]);      //note lowest is 1 based array therefore [1,i]
//            System.out.println ("->"+a[i]+" "+j);
            maxLisLength = Math.max (j + 1, maxLisLength);
            //new lisLength is of length j+1
            lowest[j + 1] = Math.min (lowest[j + 1], a[i]);
        }
        return maxLisLength;
    }

    //return 0 if no predecessor found
    //returns max index of a "strict" predecessor
    private static int findMaxPredecessor(int[] a, int lo, int hi, int key)
    {

        if (lo > hi)
        {
            return 0;
        }
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key)
        {
            //a[mid] is predecessor
            return Math.max (mid, findMaxPredecessor (a, mid + 1, hi, key));
        }
        else if (a[mid] > key)
        {
            return findMaxPredecessor (a, lo, mid - 1, key);
        }
        else   //a[mid]==key therefore mid-1 is max index of a predecessor, since a[mid-1] != key since sorted
        //in stricly inc order
        {
            return mid-1;
        }
    }
    /*
    //can also print lis (nlogn)
    public static int lis(int a[])
    {
        int n = a.length;
        int indexOfLowest[] = new int[n + 1]; //now
        Arrays.fill (indexOfLowest, Integer.MAX_VALUE);
        indexOfLowest[0] = -1; //for pred case
        indexOfLowest[1] = 0;
        int maxLisLength = 1;
        int pred[] = new int[n];
        pred[0] = -1;
        for (int i = 1; i < n; i++)
        {
            //find largest j such that a[lowest[[j]] < a[i]
            //a[lowest[[j]] is also sorted since a[lowest[[j]] will be appended to a subsequence of length j-1
            //say ending at k and therefore k<a[lowest[[j]]
            //and a[lowest[j-1]]<=k, hence a[lowest[j-1]] <=k < a[lowest[[j]]
            //hence a[lowest[[j-1]]<a[lowest[[j]]
            //hence we can binary search over a[lowest[[j]] to find max. predecessor of a[i]
            int j = findMaxPredecessor2 (indexOfLowest, a, 1, i, a[i], maxLisLength);
//            System.out.println ("->"+a[i]+" "+j);



            //new lisLength is of length j+1
            if(j==maxLisLength || a[i] < a[indexOfLowest[j+1]])
            {
                indexOfLowest[j+1] = i;
                maxLisLength = Math.max (maxLisLength, j+1);
            }
            if(j!=0)
                pred[i] = a[indexOfLowest[j]];
        }
        return maxLisLength;

    }

    //return 0 if no predecessor found
    //returns max index of a "strict" predecessor
    private static int findMaxPredecessor2(int[] indexOfLowest, int[] a, int lo, int hi, int key, int maxLisLength)
    {

        int mid = lo + (hi - lo) / 2;
        if (lo > hi || mid>maxLisLength)
        {
            return 0;
        }
        if (a[indexOfLowest[mid]] < key)
        {
            //a[mid] is predecessor
            return Math.max (mid, findMaxPredecessor2 (indexOfLowest, a, mid + 1, hi, key, maxLisLength));
        }
        else if (a[indexOfLowest[mid]] > key)
        {
            return findMaxPredecessor2 (indexOfLowest, a, lo, mid - 1, key, maxLisLength);
        }
        else   //a[mid]==key therefore mid-1 is max index of a predecessor, since a[mid-1] != key since sorted
        //in stricly inc order
        {
            return mid-1;
        }
    }
    */
}
