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].
100
36 48 92 87 28 85 42 10 44 41 39 3 79 9 14 56 1 16 46 35 93 8 82 26 100 59 60 2 96 52 13 98 70 81 71 94 54 91 17 88 33 30 19 50 18 73 65 29 78 21 61 7 99 97 45 89 57 27 76 11 49 72 84 69 43 62 4 22 75 6 66 83 38 34 86 15 40 51 37 74 67 31 20 63 77 80 12 53 5 25 58 90 68 24 64 23 95 32 55 47
 5
4 2 1 3 5
 10
1 9 8 10 2 3 4 6 5 7
 50
12 24 42 43 36 3 40 29 7 34 10 13 28 9 35 23 25 21 19 4 20 18 11 38 41 48 6 46 33 17 31 37 2 30 32 44 45 5 47 49 16 15 50 27 26 14 39 22 1 8

16
 3
 6
 13

import java.io.*;
import java.lang.*;
import java.util.*;
import java.math.*;
 
public class code
{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 

     static class FastWriter
    {
        OutputStream os;

        public FastWriter()
        {
            os = new BufferedOutputStream(System.out);
        }

        void println(String content)throws IOException
        {
            print(content);
            print("\n");
        }

        void print(String content)throws IOException
        {
            os.write(content.getBytes());
        }

        void flush()throws IOException
        {
            os.flush();
        }
    }
    
    static long P = 1000000007L;
    public static void main(String args[])throws IOException
    {
        FastReader scn = new FastReader();

        int n = scn.nextInt();
        int[] list = new int[n];

        for(int i = 0; i < n; i++)
            list[i] = scn.nextInt();

        ArrayList<Integer> ans = new ArrayList<>();
        ans.add(list[0]);
        int size = 1;

        for(int i = 1; i < n; i++)
        {
            if(list[i] > ans.get(size-1))
            {
                ans.add(list[i]);
                size++;
            }
            else if(list[i] == ans.get(size - 1))
            {

            }
            else
            {
                int index = getMoreThanIndex(ans, list[i], 0, size - 1);
                ans.set(index, list[i]);
            }
        }

        System.out.println(ans.size());
    }

    public static int getMoreThanIndex(ArrayList<Integer> list, int value, int l, int r)
    {
        while( l <= r)
        {
            int middle = (l+r)/2;
 
            if(list.get(middle) == value)
                return middle;
            else if(list.get(middle)< value)
                l = middle + 1;
            else
                r = middle - 1;
        } 
        return l;
    }

    // public static long dfs(Node current, int l, int r, Node[] nodes)
    // {
    //     current.visited = true;
        
    //     long ans = 1;
    //     for(Node next: current.neighbors)
    //     {
    //         if(!next.visited && next.sorted_index <= r && next.sorted_index >= l)
    //         {
    //             long p = dfs(next, l, r, nodes);
    //             ans = (ans * ( p + 1))%P;
    //         }
    //     }

    //     current.visited = false;
    //     return ans;
    // }
}

class Pair
{
    int a, b;
    public Pair(int a, int b)
    {
        this.a = a;
        this.b = b;
    }
}

// class Node implements Comparable<Node>
// {
//     int weight;
//     int sorted_index;
//     ArrayList<Node> neighbors;
//     boolean visited;
//     public Node()
//     {
//         neighbors = new ArrayList<>();
//     }

//     public int compareTo(Node n)
//     {
//         return this.weight - n.weight;
//     }
 
// }
 
// class MutableInt
// {
//     int count;
//     ArrayList<Integer> list;
//     public MutableInt()
//     {
//         list = new ArrayList<>();
//     }
// }

// class TrieNode
// {
//     HashMap<Character, TrieNode> map;
//     boolean visited;
//     int cost;

//     public TrieNode()
//     {
//         map = new HashMap<>();
//     }

//     public TrieNode add(char c, boolean isGood, MutableInt result, int k)
//     {
//         if(map.containsKey(c))
//         {
//             TrieNode n = map.get(c);
//             return n;
//         }
//         else
//         {
//             TrieNode n = new TrieNode();
//             if(!isGood)
//                 n.cost = this.cost + 1;
//             else
//                 n.cost = this.cost;

//             if(n.cost <= k)
//                 result.count = result.count + 1;

//             map.put(c, n);
//             return n;
//         }
//     }
// }