!ТОЧНО РАБОТАЕТ E4: Наибольшая возрастающая подпоследовательность

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

vector<int> a;

bool argSortLess(int x, int y) {
    return a[x] < a[y];
}

void update(int indx, vector<int> &p) {
    if (indx == 0)
        return;
    int parent = (indx - 1) / 2;
    p[parent] = p[2 * parent + 1] > p[2 * parent + 2] ? p[2 * parent + 1] : p[2 * parent + 2];
    update(parent, p);
}

int getMax(int node, int l, int r, int tl, int tr, vector<int> &p) {
    if (l > r)
        return -1;
    if (l == r) {
        return p[l];
    }
    if (l == tl && r == tr) {
        return p[node];
    }
    int tm = (tl + tr) / 2;

    int m1 = getMax(2 * node + 1, l, min(tm, r), tl, tm, p);
    int m2 = getMax(2 * node + 2, max(tm + 1, l), r, tm + 1, tr, p);
    if (m1 > m2) {
        return m1;
    } else {
        return m2;
    }
}

int main() {
    ifstream fin("input.txt");
    int n;
    fin >> n;
    a.resize(n + 1);
    vector<int> argSorted(n + 1);
    vector<int> sortedByVal(n + 1);

    a[0] = INT_MIN;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
        argSorted[i] = i;
    }

    sort(argSorted.begin(), argSorted.end(), argSortLess);

    int lastIndx = 0, last = -1;
    for (int i = 0; i <= n; i++) {
        if (a[argSorted[i]] != last)
            lastIndx = i;
        sortedByVal[argSorted[i]] = lastIndx;
        last = a[argSorted[i]];
    }

    int newN = 1 << (int) ceil(log2(n + 1));
    vector<int> results(n + 1);
    vector<int> p(newN * 2 - 1, -1);
    p[newN - 1 + sortedByVal[0]] = 0;
    update(newN - 1 + sortedByVal[0], p);

    for (int i = 1; i <= n; i++) {
        p[newN - 1 + sortedByVal[i]] = (
                getMax(0, newN - 1, newN - 2 + sortedByVal[i], newN - 1, newN * 2 - 2, p) + 1);
        results[i] = p[newN - 1 + sortedByVal[i]];
        update(newN - 1 + sortedByVal[i], p);
    }

    vector<int> suba;
    int i = n;
    while (results[i] != p[0])
        i--;
    while (p[0] > 0) {
        suba.push_back(i);
        p[0]--;
        while (i > 1 && results[suba.back()] != results[i - 1] + 1)
            i--;
        i--;
    }
    ofstream fout("output.txt");
    fout << suba.size() << endl;
    for (int i = suba.size() - 1; i >= 0; i--) {
        fout << suba[i] << " ";
    }
    fout.close();
    return 0;
}