最长不下降子序列 (LIS)

#include <bits/stdc++.h>
    using namespace std;
    using i64 = long long;
    int __OneWan_2024 = [](){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        return 0;
    }();
    int main() {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0 ; i < n ; i++) {
            cin >> a[i];
        }
        vector<int> f;
        for (int i = 0 ; i < n ; i++) {
            auto it = upper_bound(begin(f), end(f), a[i]);
            if (it == end(f)) {
                f.push_back(a[i]);
            } else {
                *it = a[i];
            }
        }
        cout << f.size();
        return 0;
    }