### SORTQUERY TUTORIAL

#### Tutorial
Nhận xét về hai truy vấn $1$ và $3$ như sau:
+ Với dãy rỗng ban đầu, nếu ta chỉ thực hiện các truy vấn $1$ và $2$ thì hoàn toàn có thể dùng `std::queue` để xử lý.
+ Sau truy vấn $3$, và theo sau đó là một dãy các truy vấn $1$ thì ta có thể thấy, dãy hiện tại sẽ có hai phần gồm phần tiền tố đã được sắp xếp *(dãy sau khi thực hiện truy vấn $3$ gần nhất)* và phần hậu tố vẫn giữ nguyên.

Với nhận xét trên, ta sẽ lưu dãy số trên vào hai dãy riêng:
+ Dãy $A$ gồm các phần tử của tiền tố đã được sắp xếp.
+ Dãy $B$ gồm các phần tử được thêm vào sau truy vấn $3$ gần nhất.

Dãy $A$ sẽ dùng cấu trúc dữ liệu `std::priority_queue` để lưu, còn dãy $B$ dùng `std::queue`.

Khi có truy vấn $1$, ta thêm phần tử mới vào cuối dãy $B$.

Khi có truy vấn $3$, ta lấy các phần tử trong $B$ và lần lượt thêm vào $A$, sau đó xóa ( $pop$ ) hết các phần tử trong $B$ đi.

Khi có truy vấn $2$, nếu như dãy ban đầu chưa từng được sắp xếp hoặc $A$ đang rỗng thì ta sẽ lấy phần tử đầu tiên của $B$ và xóa phần tử đó đi, ngược lại ta lấy phần tử đầu tiên của $A$ và xóa phần tử đó đi.

#### Độ phức tạp
Dễ dàng thấy được:
+ Khi thực hiện truy vấn $1$ phần tử được thêm vào dãy $B$ một lần, và sẽ được lấy ra khỏi $B$ tối đa một lần trong tương lai.
+ Khi thực hiện truy vấn $3$ phần tử trong dãy $B$ được lấy ra đúng một lần để thêm vào dãy $A$ và xóa đi.
+ Khi thực hiện truy vấn $2$, thì mỗi phần tử ở dãy $A$ hoặc $B$ đều được lấy ra tối đa một lần và bị xóa.

Nên độ phức tạp thời gian sẽ là $O(QlogQ)$ và độ phức tạp không gian là $O(Q)$.
:::spoiler Cài đặt

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;
 
priority_queue<ll, vector <ll>, greater <ll>> pq;
queue <ll> q;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    ll qr;
    cin >> qr;
    while (qr --) {
        ll t, x;
        cin >> t;
        if (t == 1) {
            cin >> x;
            q.push(x);
        }
 
        if (t == 2) {
            if (pq.empty())
                cout << q.front() << '\n', q.pop();
            else
                cout << pq.top() << '\n', pq.pop();
        }
 
        if (t == 3)
            while (q.size()) pq.push(q.front()), q.pop();
    }
 
    return 0;
}    

:::