In order to process each operation in \(O(1+\min\lbrace l _ i,l _ {s _ i}\rbrace\log N)\) time, it is a good idea to use a balanced binary search tree or a linked list.

For example, one can use std::set to manage \(\bigl\lbrace(i,A _ i)\bigr\rbrace\) and \(\bigl\lbrace(A _ i,i)\bigr\rbrace\) in order to process each query fast enough.

The following is sample code. In the sample code below, we manage \(\bigl\lbrace(A _ i,i)\bigr\rbrace\) with two balanced binary trees so that we can instantly compare an element with the median of \(x _ i\) (even without such trick, it is still fast enough to scan from the both ends and determine which reaches the boundary “\(x\) or larger” earlier).

#include <set>
#include <utility>
#include <iterator>
#include <iostream>
#include <vector>
#include <ranges>


// A class that manages a sequence.
// The following operations can be done in O(log N) time:
//  - Remove the first / last element
//  - Remove the smallest / largest element
//  - Push an element to the head / tail
//  - Retrieve the smallest / largest element
//  - Retrieve the median
//
// (More precisely, it stores a set of pairs (i, v) and manages minimum / maximum i and minimum / maximum / median of v)
class sequence {
  public:
    using value_type = std::pair<unsigned, unsigned>;
    std::set<value_type> original, small, large;

    // Balances the sizes of the two sets to support median retrieval
    void balance() {
        while (std::size(small) > std::size(large)) {
            large.emplace_hint(std::begin(large), *std::prev(std::end(small)));
            small.erase(std::prev(std::end(small)));
        }
        while (std::size(small) + 1 < std::size(large)) {
            small.emplace_hint(std::end(small), *std::begin(large));
            large.erase(std::begin(large));
        }
    }

    value_type pop_helper(unsigned i, unsigned v) {
        original.erase(std::make_pair(i, v));
        small.erase(std::make_pair(v, i));
        large.erase(std::make_pair(v, i));
        balance();
        return {i, v};
    }

public:
    void swap(sequence &rhs) {
        using std::swap;
        swap(original, rhs.original);
        swap(small, rhs.small);
        swap(large, rhs.large);
    }

    sequence() = default;

    auto min() const {
        return std::begin(std::empty(small) ? large : small)->first;
    }

    auto mid() const {
        return std::begin(large)->first;
    }

    auto max() const {
        return std::prev(std::end(large))->first;
    }

    void emplace(unsigned long i, unsigned long v) {
        original.emplace(i, v);
        (v < mid() ? small : large).emplace(v, i);
        balance();
    }

    void emplace(const value_type &value) {
        emplace(value.first, value.second);
    }

    auto empty() const noexcept {
        return std::empty(original);
    }

    auto size() const noexcept {
        return std::size(original);
    }

    auto pop_front() {
        const auto[i, v]{*begin(original)};
        return pop_helper(i, v);
    }

    auto pop_back() {
        const auto[i, v]{*std::prev(std::end(original))};
        return pop_helper(i, v);

    }

    auto pop_min() {
        const auto[v, i]{*std::begin(std::empty(small) ? large : small)};
        return pop_helper(i, v);
    }

    auto pop_max() {
        const auto[v, i]{*std::prev(std::end(large))};
        return pop_helper(i, v);
    }
};

int main() {
    using namespace std;
    unsigned N;
    cin >> N;

    vector<sequence> sequences(1);
    for (unsigned a; const auto i : views::iota(0U, N)) {
        cin >> a;
        sequences.front().emplace(i, a); // Insert the i-th element A[i]
    }

    unsigned Q;
    cin >> Q;
    sequences.resize(1 + Q);
    for (unsigned t, s, x; const auto i : views::iota(1U, 1 + Q)) {
        cin >> t >> s >> x;
        if (t == 1) { // Transfer the elements later than the x-th
            const auto M{size(sequences[s])};
            if (2 * x < M) { // If the remaining elements are fewer than transferred,
                swap(sequences[s], sequences[i]); // swap them;
                for (const auto _ : views::iota(0U, x)) // for each of the first x elements,
                    sequences[s].emplace(sequences[i].pop_front()); // transfer it from the first element in order;
            } else if (x < M)
                for (const auto _ : views::iota(x, M)) // for each of the last x elements,
                    sequences[i].emplace(sequences[s].pop_back()); // 後ろから順に移動
        } else { // transfer it from the last element in order
            if (x < sequences[s].mid()) { // If x is less than the median,
                swap(sequences[s], sequences[i]); // swap them;
                while (!empty(sequences[i]) && sequences[i].min() <= x) // while an element not exceeding x remains,
                    sequences[s].emplace(sequences[i].pop_min()); // transfer it from the smallest element in order;
            } else
                while (!empty(sequences[s]) && sequences[s].max() > x) // while an element greater than x remains,
                    sequences[i].emplace(sequences[s].pop_max()); // transfer it from the largest elment in order.
        }
        cout << size(sequences[i]) << endl; // Print the size of sequence i
    }
    return 0;
}