C++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < nums.size(); ++i) {
        cin >> nums[i];
    }

    vector<int> res;
    res.push_back(nums[0]);
    for (int i = 1; i < nums.size(); ++i) {
        int num = nums[i];
        if (num > res.back()) {
            res.push_back(num);
        } else {
            *lower_bound(res.begin(), res.end(), num) = num;
        }
    }
    cout << res.size() << endl;

    return 0;
}