for (int i = 0; i < n; ++i) {
    cin >> a[i];
}

vector<int> lis; // Lưu dãy con tăng dài nhất

for (int i = 0; i < n; ++i) {
    auto it = lower_bound(lis.begin(), lis.end(), a[i]);
    if (it == lis.end()) {
        lis.push_back(a[i]);
    } else {
        *it = a[i];
    }
}

cout << lis.size() << endl;
return 0;