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

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;  
using namespace std;
 
#define int                 long long int
#define ull                 unsigned int
#define ld                  long double
#define pb                  push_back
#define ff                  first
#define ss                  second
#define S(arr)              sort(arr.begin(),arr.end());
#define RS(arr)              sort(arr.rbegin(),arr.rend());
#define R(arr)              reverse(arr.begin(),arr.end());
#define si                  set <int>
#define vi                  vector <int>
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define vvi                 vector <vector <int>>
#define vs                  vector <string>
#define pii                 pair <int, int>
#define vpi                 vector <pii>
#define vpp                 vector <pair<int, pii>>
#define mii                 map <int, int>
#define mci                 map<char, int>
#define mpi                 map <pii, int>
#define spi                 set <pii>
#define speed               ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl                "\n"
#define all(p)              p.begin(), p.end()
#define T                   int tcf;cin>>tcf;while(tcf--)
#define que_max(t)          priority_queue <t>
#define que_min(t)          priority_queue <t, vector<t>, greater<t>>
#define dba(a, l, r)        for(auto x:a)cout<<x<<" ";cout<<endl;
#define db1(x)              cout << #x " = " << x << endl;
#define db2(x,y)            cout << #x " = " << x << " " << #y " = " << y << endl;
#define db3(x,y,z)          cout << #x " = " << x << " " << #y " = " << y << " " << #z " = " << z << endl;
#define db4(x,y,z,w)        cout << #x " = " << x << " " << #y " = " << y << " " << #z " = " << z << " " << #w " = " << w << endl;
#define db5(x,y,z,w,v)      cout << #x " = " << x << " " << #y " = " << y << " " << #z " = " << z << " " << #w " = " << w << " " << #v " = " << v << endl;
#define db6(x,y,z,w,v,a) db3(a, y, x)db3(w, v, a)
#define p2d(v)              for(auto a:v){for(auto b:a)cout<<b<<" ";cout<<endl;}
#define p1d(v)              for(auto a:v)cout<<a<<" ";cout<<endl;
#define ppi(v)              for(auto a:v)cout<<a.ff<<" "<<a.ss<<endl;


typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
void read(int n=10){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout<<setprecision(n)<<fixed;
    #ifndef ONLINE_JUDGE
         freopen("input.txt",  "r",  stdin);
         freopen("output.txt", "w", stdout);
    #endif
}
 
int M = 1e9 + 7;
int M1 = 998244353;
#define qqq 4000005
#define pi 3.14159265358979323851
 
pii dfs(int curr,int parent,vvi & graph,vi & visited){
    visited[curr] = 1;
    int inc = 1,nic = 0;
    for(auto a:graph[curr]){
        if(a==parent)
            continue;
        if(!visited[a]){
            pii temp = dfs(a,curr,graph,visited);
            nic += temp.ff;
            inc += temp.ss;
        }
    }
    return {inc,nic};
}
 
int32_t main(){
    read();
    int n;
    cin>>n;
    vi arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vvi graph(n+1);
    for(int i=0;i<n-1;i++){
        if(arr[i]>arr[i+1]){
            swap(arr[i],arr[i+1]);
            graph[arr[i]].pb(arr[i+1]);
            graph[arr[i+1]].pb(arr[i]);
        }
    }
    vi visited(n+1);
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            pii temp = dfs(i,0,graph,visited);
            ans+=max(temp.ss,temp.ff);
        }
    }
    cout<<ans;
}  