#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <functional>
#include <string>
using namespace std;
#define INF 987654321
vector<int> v;
int bs(int x,int l,int h) {
while (l <= h) {
if (l == h) return l+1;
int mid = (l + h) / 2;
if (v[mid] < x) {
l = mid + 1;
}
else
h = mid - 1;
}
return l;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (v.empty()) { //비어있으면 삽입
v.push_back(x);
}
else {
int idx = bs(x, 0, v.size());
if (idx >= v.size()) v.push_back(x);
else {
if (v[idx] > x && v[idx-1]<x) v[idx] = x;
else if (v[idx] > x && v[idx - 1] > x) v[idx - 1] = x;
//idx가 현재 사이즈보다 작을 경우
}
}
}
cout << v.size() << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8c3RyaW5nPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBJTkYgOTg3NjU0MzIxCgp2ZWN0b3I8aW50PiB2OwoKaW50IGJzKGludCB4LGludCBsLGludCBoKSB7Cgl3aGlsZSAobCA8PSBoKSB7CgkJaWYgKGwgPT0gaCkgcmV0dXJuIGwrMTsKCQlpbnQgbWlkID0gKGwgKyBoKSAvIDI7CgkJaWYgKHZbbWlkXSA8IHgpIHsKCQkJbCA9IG1pZCArIDE7CgkJfQoJCWVsc2UKCQkJaCA9IG1pZCAtIDE7Cgl9CglyZXR1cm4gbDsKfQppbnQgbWFpbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CgljaW4udGllKDApOwoJY291dC50aWUoMCk7CglpbnQgbjsKCWNpbiA+PiBuOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQlpbnQgeDsKCQljaW4gPj4geDsKCQlpZiAodi5lbXB0eSgpKSB7IC8v67mE7Ja07J6I7Jy866m0IOyCveyehQoJCQl2LnB1c2hfYmFjayh4KTsKCQl9CgkJZWxzZSB7CgkJCWludCBpZHggPSBicyh4LCAwLCB2LnNpemUoKSk7CgkJCWlmIChpZHggPj0gdi5zaXplKCkpIHYucHVzaF9iYWNrKHgpOwoJCQllbHNlIHsKCQkJCWlmICh2W2lkeF0gPiB4ICYmIHZbaWR4LTFdPHgpIHZbaWR4XSA9IHg7CgkJCQllbHNlIGlmICh2W2lkeF0gPiB4ICYmIHZbaWR4IC0gMV0gPiB4KSB2W2lkeCAtIDFdID0geDsKCQkJCS8vaWR46rCAIO2YhOyerCDsgqzsnbTspojrs7Tri6Qg7J6R7J2EIOqyveyasAoJCQl9CgkJfQoJfQoKCWNvdXQgPDwgdi5zaXplKCkgPDwgZW5kbDsKCglyZXR1cm4gMDsKfQ==