Code : D. Longest Max Min Subsequence

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<bool> is_last_occ(n);
    set<int> present;
    for (int i = n - 1; i >= 0; i--) {
        if (!present.count(a[i])) {
            is_last_occ[i] = true;
            present.insert(a[i]);
        }
    }

    set<int> taken, available;
    vector<int> res;
    vector<vector<int>> indices(n + 1);

    bool take_big = true;
    int cur = -1;
    for (int i = 0; i < n; i++) {
        if (taken.count(a[i])) {
            continue;
        }

        available.insert(a[i]);
        indices[a[i]].push_back(i);

        if (!is_last_occ[i]) {
            continue;
        }

        while (!taken.count(a[i])) {
            int ele;
            if (take_big) {
                ele = *available.rbegin();
                while (indices[ele].back() < cur) {
                    available.erase(ele);
                    ele = *available.rbegin();
                }
            } else {
                ele = *available.begin();
                while (indices[ele].back() < cur) {
                    available.erase(ele);
                    ele = *available.begin();
                }
            }

            cur = *upper_bound(indices[ele].begin(), indices[ele].end(), cur);
            take_big = !take_big;
            available.erase(ele);
            taken.insert(ele);
            res.push_back(ele);
        }
    }

    cout << res.size() << "\n";
    for (auto &ele : res) {
        cout << ele << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
}

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<bool> is_last_occ(n);
    set<int> present;
    for (int i = n - 1; i >= 0; i--) {
        if (!present.count(a[i])) {
            is_last_occ[i] = true;
            present.insert(a[i]);
        }
    }

    set<int> taken, available;
    vector<int> res;
    vector<vector<int>> indices(n + 1);

    int cur = -1;
    for (int i = 0; i < n; i++) {
        if (taken.count(a[i])) {
            continue;
        }

        available.insert(a[i]);
        indices[a[i]].push_back(i);

        if (!is_last_occ[i]) {
            continue;
        }

        while (!taken.count(a[i])) {
            int ele = *available.begin();
            while (indices[ele].back() < cur) {
                available.erase(ele);
                ele = *available.begin();
            }

            cur = *upper_bound(indices[ele].begin(), indices[ele].end(), cur);
            available.erase(ele);
            taken.insert(ele);
            res.push_back(ele);
        }
    }

    cout << res.size() << "\n";
    for (auto &ele : res) {
        cout << ele << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
}

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

int op(int l, int r) { return min(l, r); }
int e() { return 1e9; }

void solve(vector<int> &a) {
    int n = a.size();

    segtree<int, op, e> seg_min(a);

    map<int, deque<int>> pos;
    for (int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }
    set<int> last;
    for (const auto &[_, vs] : pos) {
        last.insert(vs.back());
    }
    int m = last.size();

    vector<int> ans;
    for (int i = 0, l = 0; i < m; ++i) {
        const auto r = *last.begin();
        const auto v = seg_min.prod(l, r + 1);
        ans.push_back(v);
        last.erase(pos[v].back());
        for (const auto i : pos[v]) {
            seg_min.set(i, e());
        }
        while (pos[v].front() < l) {
            pos[v].pop_front();
        }
        l = pos[v].front();
        pos.erase(v);
    }

    cout << ans.size() << "\n";
    for (auto &ele : ans) {
        cout << ele << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
}

// Credits : nskybytskyi

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<bool> is_last_occ(n);
    vector<bool> present(n + 1, false);
    for (int i = n - 1; i >= 0; i--) {
        if (!present[a[i]]) {
            is_last_occ[i] = true;
            present[a[i]] = true;
        }
    }

    stack<int> stk;
    vector<int> index_in_stack(n + 1, -1);

    int locked_index = -1;
    for (int i = 0; i < n; i++) {
        if (index_in_stack[a[i]] == -1) {
            while (!stk.empty() && stk.top() > locked_index &&
                   a[stk.top()] > a[i]) {
                index_in_stack[a[stk.top()]] = -1;
                stk.pop();
            }

            stk.push(i);
            index_in_stack[a[i]] = i;
        }

        // If element is present, from exchange argument, we need to reject the
        // new element, hence we don't push anything on the stack.

        // At every red index, stack is locked at the first occurrence of red.
        // No one can pop further than that.
        if (is_last_occ[i]) {
            locked_index = max(locked_index, index_in_stack[a[i]]);
        }
    }

    vector<int> res;
    while (!stk.empty()) {
        res.push_back(a[stk.top()]);
        stk.pop();
    }
    reverse(res.begin(), res.end());

    cout << res.size() << "\n";
    for (auto &ele : res) {
        cout << ele << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
}