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>
using namespace std;
template <typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename F, typename S>
ostream &operator<<(ostream &os, const map<F, S> &v) {
  os << "[";
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << ", ";
    os << it->first << " = " << it->second;
  }
  return os << "]";
}
void faltu() { cerr << endl; }
template <typename T>
void faltu(T a[], int n) {
  for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
  cerr << endl;
}
template <typename T, typename... hello>
void faltu(T arg, const hello &...rest) {
  cerr << arg << ' ';
  faltu(rest...);
}
const int fx[] = {+1, -1, +0, +0};
const int fy[] = {+0, +0, +1, -1};
long long Set(long long &N, long long pos) { return N = N | (1ll << pos); }
long long Reset(long long &N, long long pos) { return N = N & ~(1ll << pos); }
bool check(long long N, long long pos) { return (bool)(N & (1ll << pos)); }
void INITIALIZE() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
inline long long add(long long a, long long b) {
  return (a + b >= 1000000007) ? (a + b - 1000000007) : (a + b);
}
inline long long sub(long long a, long long b) {
  return (a - b < 0) ? (a - b + 1000000007) : (a - b);
}
inline long long mul(long long a, long long b) {
  return (a * 1ll * b) % 1000000007;
}
void Binary(long long x) {
  for (int i = 31; i >= 0; i--) {
    if ((1 << i) & x)
      cerr << "1";
    else
      cerr << "0";
  }
  cerr << "\n";
}
long long ncr(long long n, long long r) {
  long long ans = 1;
  if (r > n - r) r = n - r;
  for (long long i = 1; i <= r; i++) {
    ans *= (n - i + 1), ans /= i;
  }
  return ans;
}
long long pow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % 1000000007;
    b >>= 1;
    a = (a * a) % 1000000007;
  }
  return res;
}
const long long mxn = 2e10 + 5;
vector<long long> bit(10);
long long n;
void update(long long pos, long long val) {
  for (; pos <= n; pos += pos & -pos) bit[pos] = max(bit[pos], val);
}
long long query(long long pos) {
  long long ans = 0;
  for (; pos; pos -= pos & -pos) ans += bit[pos];
  return ans;
}
void solve() {
  cin >> n;
  long long mx = 0;
  for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    long long koita = query(x);
    mx = max(mx, koita + 1);
    update(x, koita + 1);
  }
  cout << mx << endl;
}
int main() {
  INITIALIZE();
  int t;
  t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
