omg debug doesn't work...

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <ctime>
#include <numeric>


#ifndef M_PI
#define M_PI 3.141592653589
#endif
#define int long long
#define double long double

#ifdef TIME
#define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false);int32_t START = clock()
#define finish cout << "\ntime: " << (clock() - START) / (CLOCKS_PER_SEC * 1.0); return 0
#endif

#ifndef TIME
#define start cin.tie(NULL); cout.tie(NULL); cout.setf(ios::fixed); cout.precision(10); ios_base::sync_with_stdio(false)
#define finish return 0
#endif

using namespace std;


//vector input
template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &i : vec) {
        cin >> i;
    }
    return is;
}

//pair output
template<typename E>
ostream &operator<<(ostream &os, pair<E, E> &t) {
    os << t.first << ' ' << t.second;
    return os;
}

//"map" pair output
template<typename E>
ostream &operator<<(ostream &os, pair<const E, E> &t) {
    os << t.first << ' ' << t.second;
    return os;
}

//vector output
template<typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
    for (T i : vec) {
        os << i << ' ';
    }
    return os;
}

//2 dimensional vector output
template<typename T>
ostream &operator<<(ostream &os, vector<vector<T> > &vec) {
    for (vector<T> i : vec) {
        os << i << '\n';
    }
    return os;
}

struct segtree {
    struct node {
        int mx;
        int cnt;

        node() {
            mx = 0;
            cnt = 1;
        }

        node(int m, int c) {
            mx = m;
            cnt = c;
        }

        node operator+(node &b) const {
            if (mx > b.mx) {
                return {mx, cnt};
            } else if (mx == b.mx) {
                return {mx, cnt + b.cnt};
            } else {
                return {b.mx, b.cnt};
            }
        }
    };

    int n;
    vector<node> tree;

    segtree(int nn) {
        tree.resize(2 * nn);
        n = nn;
    }

    void set(int i, int x, int am) {
        i += n;
        node to_be_added = node(x, am);
        tree[i] = tree[i] + to_be_added;
        i /= 2;
        while (i != 0) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
            i /= 2;
        }
    }

    pair<int, int> get(int l, int r) {
        l += n;
        r += n;
        node ans;
        while (l <= r) {
            if (l % 2 == 1) {
                ans = ans + tree[l];
                l += 1;
            }
            if (r % 2 == 0) {
                ans = ans + tree[r];
                r -= 1;
            }
            l /= 2;
            r /= 2;
        }
        return {ans.mx, ans.cnt};
    }
};

int32_t main() {
    start;

    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    vector<int> coords = a;

    sort(coords.begin(), coords.end());
    coords.resize(distance(coords.begin(), unique(coords.begin(), coords.end())));

    for (int i = 0; i < n; ++i) {
        a[i] = distance(coords.begin(), lower_bound(coords.begin(), coords.end(), a[i]));
    }

    cout << a << '\n';

    segtree sgt(coords.size());

    for (int i = 0; i < n; ++i) {
        auto [ans, amount] = sgt.get(0, a[i] - 1);
        sgt.set(i, ans + 1, amount);
    }

    cout << sgt.get(0, coords.size() - 1).second << '\n';

    finish;
}