/*
最長部分増加列の長さを求める
LIS(A,true):配列Aの狭義最長部分増加列の長さを返す
LIS(A,false):配列Aの広義最長部分増加列の長さを返す
*/
template <typename T>
struct segment_tree
{
private:
    using FX = function<T(T, T)>;
    int n;
    T id;
    vector<T> data;
    FX fx, gx; //区間操作, 点更新操作用
    //[a,b)に対する区間操作　kは[l,r)に対するデータを保持する
    T sub_query(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
            return id;
        if (a <= l && r <= b)
            return data[k];
        T L = sub_query(a, b, 2 * k + 1, l, (l + r) / 2); //左の子
        T R = sub_query(a, b, 2 * k + 2, (l + r) / 2, r); //右の子
        return fx(L, R);
    }

public:
    segment_tree(int n0, T id0, FX fx0, FX gx0) : n(1), id(id0), fx(fx0), gx(gx0)
    {
        while (n < n0)
            n *= 2;
        data.resize(2 * n - 1, id); //単位元で初期化
    }
    //1点更新クエリの場合はgxを省略できるように
    segment_tree(int n0, T id0, FX fx0) : segment_tree(n0, id0, fx0, [](T a, T b) { return b; }) {}
    //配列Aの値で初期化する
    void build(vector<T> A)
    {
        T siz = A.size();
        for (int i = 0; i < siz; i++)
            data[i + n - 1] = A[i];
        for (int i = n - 2; i >= 0; i--)
            data[i] = fx(data[2 * i + 1], data[2 * i + 2]);
    }
    void update(int i, T x)
    {
        i += n - 1;
        data[i] = gx(data[i], x);
        while (i > 0)
        {
            i = (i - 1) / 2;                                //親へ
            data[i] = fx(data[2 * i + 1], data[2 * i + 2]); //子ノードで更新
        }
    }
    T query(int l, int r) { return sub_query(l, r + 1, 0, 0, n); } //根からスタート
    //data[x]またはdata.at(x)でアクセスできるように
    T operator[](int i) { return data[i + n - 1]; }
    T at(int i) { return data[i + n - 1]; }
};
template <typename T>
void press(vector<T> &A)
{
    vector<T> sorted = A;
    sort(sorted.begin(), sorted.end());
    auto itr = unique(sorted.begin(), sorted.end());
    sorted.erase(itr, sorted.end());
    for (int i = 0; i < A.size(); i++)
        A[i] = lower_bound(sorted.begin(), sorted.end(), A[i]) - sorted.begin();
    return;
}
//配列Aの最長増加部分列の長さを求める
template <typename T>
T LIS(vector<T> A, bool strict)
{
    int n = A.size();
    vector<T> B = A;
    press(B);
    auto fx = [](T x, T y) { return max(x, y); };
    T id = numeric_limits<T>::lowest();
    segment_tree<T> tree(n + 1, id, fx);
    vector<T> resiz(n + 1, 0);
    tree.build(resiz);
    T ret = 0;
    for (int i = 0; i < n; i++)
    {
        T maxx;
        if (strict)
            maxx = tree.query(0, B[i]);
        else
            maxx = tree.query(0, B[i] + 1);
        if (tree[B[i] + 1] < maxx + 1)
        {
            tree.update(B[i] + 1, maxx + 1);
            ret = max(ret, maxx + 1);
        }
    }
    return ret;
}