堆与 priority_queue

// 标准答案 —— 完全不建堆：把数原样堆在一个 vector 里，每次要最小值就**整个扫一遍**
//
// 为什么它存在：正解（二叉堆）想的是「维护一棵完全二叉树，把顺序信息一路攒下来」。
// 要是标准答案也维护一棵堆，两份代码就是同一个思路写了两遍 ——
// 只能验出打字错误，验不出想法错误（第 9、15、34、35、36 章那条）。
//
// 所以这一份**一点结构都不攒**：插入就是往后一放，查询/删除就是从头到尾扫一遍找最小的那个。
//
// ★ 扫的时候**一次 break 都没有**：哪怕第一个就是最小的，也要把整个数组走完。
//   （第 31 章：「找到第一个就 break」会让暴力假装自己不慢；
//    第 35 章补的后半句：标准答案要挑「没有 break」的那个思路。）
//
// ⚠ 「删除最小值」这里用的是 erase（把后面整段往前搬），也是实打实的 O(n) ——
//   不许用「和末尾交换再 pop_back」那种小聪明，那样就不是「什么都不攒」了
//   （交换会打乱顺序，而顺序是这份代码唯一还剩的东西：最后一行要按从小到大输出）。
//
// 复杂度 O(n²)。
//
// 输入：第一行 n（操作条数）；接下来 n 行，每行是
//       "1 x"（插入 x）/ "2"（输出当前最小值）/ "3"（删除当前最小值）。
// 输出：每个 "2" 一行 —— 当前最小值，★ 堆为空时输出一个 E；
//       ★ 最后再输出一行：堆里剩下的元素**从小到大**全部列出来（空堆输出一个 -）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> a;                       // 就是一堆数，谁前谁后毫无意义
    string out;

    auto minPos = [&]() {                      // ★ 从头扫到尾，中途绝不 break
        int p = 0;
        for (int i = 1; i < (int)a.size(); i++)
            if (a[i] < a[p]) p = i;
        return p;
    };

    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            long long x;
            cin >> x;
            a.push_back(x);
        } else if (op == 2) {
            if (a.empty()) out += "E\n";       // ⚠ 空堆是题面允许的，不是「不会发生」
            else { out += to_string(a[minPos()]); out += '\n'; }
        } else {
            if (a.empty()) continue;           // 空堆删除：什么都不做
            a.erase(a.begin() + minPos());     // O(n) 的搬运，一点便宜都不占
        }
    }

    sort(a.begin(), a.end());                  // ★ 最后那一行：剩下的全列出来
    if (a.empty()) out += "-\n";
    else {
        for (size_t i = 0; i < a.size(); i++) {
            if (i) out += ' ';
            out += to_string(a[i]);
        }
        out += '\n';
    }

    cout << out;
    return 0;
}

// 正解 —— 手写小根堆（完全二叉树塞进数组，上浮 / 下沉各 O(log n)）
//
// ============ 这一章的 log，是**证得死死的** ============
//
// 第 36 章那个 O(α(n)) 只能给结论 + 实测（完整证明超出这本书的范围）。
// 这一章正好反过来：两句话就证完了，而且**每一步都能在数组上数出来**。
//
//   ① 堆是一棵**完全二叉树**：除了最后一层，每层都填满，最后一层靠左。
//      于是它有多高？第 0 层 1 个、第 1 层 2 个、第 2 层 4 个……
//      前 h 层一共 2^h − 1 个点，所以 n 个点的完全二叉树高度就是 **⌊log₂ n⌋**。
//      —— 不是估的，是**数出来的**。
//   ② 上浮只往上走（每次 i → i/2），下沉只往下走（每次 i → 2i 或 2i+1），
//      两者走的都是**一条根到叶的路** —— 长度不超过树高。
//
//   ⇒ 每次 push / pop 都是 O(log n)。n = 2×10⁵ 时这个数只有 **17**。
//
// ============ 数组下标：为什么从 1 开始 ============
//
//   下标 i 的两个儿子是 2i 和 2i+1，爸爸是 i/2（整除）。
//   ⚠ 从 0 开始的话就得写成 2i+1 / 2i+2 和 (i−1)/2，能用但难记 ——
//     这一章统一 1 基（和区间类题目那条约定同源：下标从 1 开始，公式才干净）。
//
// ============ 为什么用「空穴法」而不是一路 swap ============
//
//   一次 swap 是三次赋值（tmp = a; a = b; b = tmp）。
//   可上浮 / 下沉的路上，那个被挪动的元素**最后总要落在某一格**，中间那些位置它只是路过。
//   所以正确的写法是：先把它抱在手上（int x = a[i]），沿路只把别人往它腾出来的空穴里搬，
//   最后再把它放下 —— **每层只有一次赋值，不是三次**。
//
//   ★ 这个改动**不影响任何一个答案**，只影响移动次数（实测差三倍，见 count.cpp）。
//     ⚠ 也就是说：对拍在它身上一辈子抓不到 —— 第 36 章那个「第四个盲区」在这一章又见了一次。
//
// 复杂度 O(n log n)。

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

const int MAXN = 200005;
long long a[MAXN];                             // ★ a[1..sz] 才是堆，a[0] 空着不用
int sz = 0;

/** 上浮：a[i] 比爸爸小就往上，直到爸爸不比它大（或者它已经是根） */
void up(int i) {
    long long x = a[i];                        // 抱在手上
    while (i > 1 && a[i >> 1] > x) {
        a[i] = a[i >> 1];                      // 爸爸落到空穴里
        i >>= 1;
    }
    a[i] = x;                                  // 放下
}

/** 下沉：a[i] 比儿子大就往下，★ 两个儿子里要挑**小的**那个换 */
void down(int i) {
    long long x = a[i];
    while ((i << 1) <= sz) {
        int c = i << 1;
        if (c < sz && a[c + 1] < a[c]) c++;    // ⚠ c < sz 才有右儿子（c == sz 时只有左儿子）
        if (a[c] >= x) break;                  // 已经就位，不用再往下了
        a[i] = a[c];
        i = c;
    }
    a[i] = x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    string out;
    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            long long x;
            cin >> x;
            a[++sz] = x;                       // 先放到最后一格（完全二叉树的下一个空位）
            up(sz);                            // 再上浮到该去的地方
        } else if (op == 2) {
            if (sz == 0) out += "E\n";
            else { out += to_string(a[1]); out += '\n'; }   // 堆顶就是最小值，O(1)
        } else {
            if (sz == 0) continue;
            a[1] = a[sz--];                    // ★ 拿最后一格填到根上（完全二叉树的形状不能破）
            if (sz) down(1);                   // 再把它沉到该去的地方
        }
    }

    // ★ 最后那一行：把堆里剩下的全部按从小到大倒出来 —— 就是一次堆排序
    vector<long long> rest;
    while (sz) {
        rest.push_back(a[1]);
        a[1] = a[sz--];
        if (sz) down(1);
    }
    if (rest.empty()) out += "-\n";
    else {
        for (size_t i = 0; i < rest.size(); i++) {
            if (i) out += ' ';
            out += to_string(rest[i]);
        }
        out += '\n';
    }

    cout << out;
    return 0;
}

// 同一道题，改用 STL 的 priority_queue —— 比赛里真正会写的那 3 行
//
// 为什么手写完还要写这一份：**手写是为了知道它里面在干什么，比赛里用的是这一份。**
// （第 8 章 fast.cpp / stl.cpp 那一对同款：先手写二分，再给 lower_bound。）
//
// ⚠ priority_queue 默认是**大根堆**（top() 是最大的），要小根堆得把三个模板参数写全：
//
//     priority_queue<long long, vector<long long>, greater<long long>> q;
//                    ~~~~~~~~~  ~~~~~~~~~~~~~~~~~  ~~~~~~~~~~~~~~~~~~~
//                    元素类型    底层容器（几乎总是 vector）  ★ 比较器
//
//   记不住的话有个更笨但绝不会错的办法：**存进去的时候取负，取出来再取负** ——
//   最大的 −x 就是最小的 x。（负数溢出要小心，这题 |x| ≤ 1e9 没问题。）
//
// ⚠ 它**没有**「遍历」这个操作：堆只保证 top() 是最小的，
//   底下那 n−1 个元素在数组里是什么顺序，标准不作任何承诺。
//   所以最后那一行「从小到大列出剩下的」只能一个个 pop 出来 —— 这本身就是堆排序。
//
// 三个操作：q.push(x) / q.top() / q.pop()，还有 q.empty()、q.size()。
// ★ 这一份和 fast.cpp 在 300 轮对拍里必须**逐字节相同**（check:viz 里钉着这条）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    priority_queue<long long, vector<long long>, greater<long long>> q;   // ★ 小根堆
    string out;

    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            long long x;
            cin >> x;
            q.push(x);
        } else if (op == 2) {
            if (q.empty()) out += "E\n";
            else { out += to_string(q.top()); out += '\n'; }
        } else {
            if (!q.empty()) q.pop();
        }
    }

    if (q.empty()) out += "-\n";
    else {
        bool first = true;
        while (!q.empty()) {                   // 一个个倒出来，天然就是从小到大
            if (!first) out += ' ';
            first = false;
            out += to_string(q.top());
            q.pop();
        }
        out += '\n';
    }

    cout << out;
    return 0;
}

// ★ 这一章的尺子：**数一数元素之间比了多少次、搬了多少次**
//
// 为什么它存在，有两个理由，而且是两件不同的事：
//
//   ① 秒表在这一章会失灵（第 36 章那条的第二次现场）：正解在 20 万个元素上跑完全程
//      和「只把输入读完」几乎一样快 —— `./count read` 就是用来确认这一点的。
//   ② 这张表里有一对写法**答案完全一样**（空穴法 vs 一路 swap），
//      对拍在它们身上一辈子抓不到（第 36 章那个「第四个盲区」）。
//      ★ 次数可复现，秒数不可复现（第 21 章 stairsCount.cpp 以来的老规矩）。
//
// ============ 口径（正文里也要写清楚，否则这张表没法读）============
//
//   · **比较次数** = 两个**元素**之间比大小的次数（`a[x] < a[y]` 这种）。
//     下标之间的比较（`i > 1`、`c < sz`）不算 —— 它们和数据规模无关，是循环的记账。
//   · **移动次数** = 给数组格子赋值的次数（`a[i] = …`）。
//     一次 swap 记 **3** 次（tmp = a; a = b; b = tmp），空穴法沿路每层只记 1 次。
//   · **上浮比较 / 下沉比较** 是比较次数的两半，专门拆开是因为它们的曲线**形状不同**：
//     下沉在四种数据上都要走到底，上浮只有「递减插入」那一档才顶得到 log n。
//   · ⚠ 最后那一行「把剩下的从小到大倒出来」也是实打实的开销，**照样计进去**
//     （第 29、36 章那条：量之前先确认你量的就是它，别把开销偷偷藏起来）。
//
// 用法：./count           < 数据   打印那张对比表
//       ./count read      < 数据   ★ 只把输入读完就退出，什么都不算
//       ./count csv       < 数据   同一批数字，一行一种写法，给脚本和 check:viz 读
//       ./count csv fast  < 数据   ⚠ 只跑指定的那一种写法
//                                  （量形状那张表要开到十万级，linear 是 O(n²)，跑不动）

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

// 按显示宽度补空格：ASCII 算 1 格，汉字算 2 格（setw 数的是字节，对不齐）
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

enum Mode { LINEAR, SORTED, SWAPH, FAST };

struct Bag {
    Mode mode;
    vector<long long> a;                       // LINEAR/SORTED 用它；堆用 h[1..sz]
    vector<long long> h;
    int sz = 0;
    long long cmpUp = 0, cmpDown = 0, cmpOther = 0, mov = 0;

    void init(int cap) { h.assign(cap + 2, 0); }
    long long cmp() const { return cmpUp + cmpDown + cmpOther; }

    /* ---------- 堆：空穴法（正解） ---------- */
    void upHole(int i) {
        long long x = h[i];
        while (i > 1) {
            cmpUp++;
            if (!(h[i >> 1] > x)) break;
            h[i] = h[i >> 1];                  // 只搬别人，x 还抱在手上
            mov++;
            i >>= 1;
        }
        h[i] = x;
        mov++;
    }
    void downHole(int i) {
        long long x = h[i];
        while ((i << 1) <= sz) {
            int c = i << 1;
            if (c < sz) { cmpDown++; if (h[c + 1] < h[c]) c++; }    // 两个儿子里挑小的
            cmpDown++;
            if (h[c] >= x) break;
            h[i] = h[c];
            mov++;
            i = c;
        }
        h[i] = x;
        mov++;
    }

    /* ---------- 堆：一路 swap（答案完全一样，只是搬得多） ---------- */
    void upSwap(int i) {
        while (i > 1) {
            cmpUp++;
            if (!(h[i >> 1] > h[i])) break;
            swap(h[i], h[i >> 1]);
            mov += 3;                          // ★ 一次 swap = 三次赋值
            i >>= 1;
        }
    }
    void downSwap(int i) {
        while ((i << 1) <= sz) {
            int c = i << 1;
            if (c < sz) { cmpDown++; if (h[c + 1] < h[c]) c++; }
            cmpDown++;
            if (h[c] >= h[i]) break;
            swap(h[i], h[c]);
            mov += 3;
            i = c;
        }
    }

    void push(long long x) {
        if (mode == LINEAR) { a.push_back(x); mov++; return; }
        if (mode == SORTED) {                  // 有序数组：二分找位置，再把后面整段往后挪
            int lo = 0, hi = (int)a.size();
            while (lo < hi) { int mid = (lo + hi) >> 1; cmpOther++; if (a[mid] < x) lo = mid + 1; else hi = mid; }
            a.insert(a.begin() + lo, x);
            mov += (int)a.size() - lo;         // 插入点后面的每一个都往后搬了一格
            return;
        }
        h[++sz] = x;
        mov++;
        if (mode == FAST) upHole(sz); else upSwap(sz);
    }

    int minPos() {                             // LINEAR 专用：从头扫到尾，★ 不 break
        int p = 0;
        for (int i = 1; i < (int)a.size(); i++) { cmpOther++; if (a[i] < a[p]) p = i; }
        return p;
    }

    bool empty() const { return (mode == LINEAR || mode == SORTED) ? a.empty() : sz == 0; }

    long long top() {
        if (mode == LINEAR) return a[minPos()];
        if (mode == SORTED) return a[0];
        return h[1];
    }

    void pop() {
        if (mode == LINEAR) { int p = minPos(); mov += (int)a.size() - p - 1; a.erase(a.begin() + p); return; }
        if (mode == SORTED) { mov += (int)a.size() - 1; a.erase(a.begin()); return; }
        h[1] = h[sz--];
        mov++;
        if (sz) { if (mode == FAST) downHole(1); else downSwap(1); }
    }
};

int main(int argc, char** argv) {
    // ⚠ 读入的写法必须和 fast.cpp 一字不差，否则 `./count read` 量出来的「读入要多久」
    //   和它对不上（第 32 章那条：两份代码的 I/O 设置不一致，量的是读入速度不是算法）。
    //   输出只用 printf、不用 cout，所以关掉 sync 是安全的（第 26 章那条混用的坑）。
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int, long long>> ops(n);
    int nPush = 0, nAsk = 0, nPop = 0;
    for (auto& o : ops) {
        cin >> o.first;
        o.second = 0;
        if (o.first == 1) { cin >> o.second; nPush++; }
        else if (o.first == 2) nAsk++;
        else nPop++;
    }

    if (argc > 1 && string(argv[1]) == "read") {
        printf("只读入：%d 条操作（插入 %d，查询 %d，删除 %d）—— 一次比较都没做\n",
               n, nPush, nAsk, nPop);
        return 0;
    }

    struct Row { Mode mode; const char* name; const char* note; };
    vector<Row> rows = {
        {LINEAR, "linear", "不建堆，每次扫一遍"},
        {SORTED, "sorted", "维护有序数组"},
        {SWAPH,  "swapHeap", "堆，一路 swap"},
        {FAST,   "fast",   "堆 + 空穴法（正解）"},
    };
    // ⚠ 只跑指定的那一种（linear / sorted 是 O(n²)，量形状那张表时开不到十万级）
    if (argc > 2) {
        string only = argv[2];
        vector<Row> keep;
        for (auto& r : rows) if (only == r.name) keep.push_back(r);
        if (!keep.empty()) rows = keep;
    }
    const size_t gold = rows.size() - 1;                    // 最后一行永远是当基准的那一份

    vector<long long> cmpAll(rows.size()), movAll(rows.size()), upAll(rows.size()), downAll(rows.size());
    vector<string> ans(rows.size());

    for (size_t k = 0; k < rows.size(); k++) {
        Bag b;
        b.mode = rows[k].mode;
        b.init(nPush + 2);
        string out;
        for (auto& [op, x] : ops) {
            if (op == 1) b.push(x);
            else if (op == 2) { if (b.empty()) out += "E|"; else { out += to_string(b.top()); out += '|'; } }
            else if (!b.empty()) b.pop();
        }
        // 最后那一行：把剩下的从小到大倒出来（★ 这一段的开销照样计进去）
        if (b.empty()) out += "-";
        else {
            bool first = true;
            while (!b.empty()) { if (!first) out += ' '; first = false; out += to_string(b.top()); b.pop(); }
        }
        cmpAll[k] = b.cmp();
        movAll[k] = b.mov;
        upAll[k] = b.cmpUp;
        downAll[k] = b.cmpDown;
        ans[k] = out;
    }

    if (argc > 1 && string(argv[1]) == "csv") {
        for (size_t k = 0; k < rows.size(); k++)
            printf("%s,%lld,%lld,%lld,%lld,%s\n", rows[k].name,
                   cmpAll[k], movAll[k], upAll[k], downAll[k],
                   ans[k] == ans[gold] ? "同正解" : "不同");
        return 0;
    }

    printf("%d 条操作（插入 %d，查询 %d，删除 %d）\n\n", n, nPush, nAsk, nPop);
    printf("%s  %s  %s  %s  %s  %s  %s\n",
           padDisp("写法", 10).c_str(), padDisp("说明", 22).c_str(),
           padDisp("比较次数", 12).c_str(), padDisp("移动次数", 12).c_str(),
           padDisp("其中上浮比较", 14).c_str(), padDisp("其中下沉比较", 14).c_str(),
           padDisp("答案", 8).c_str());
    for (size_t k = 0; k < rows.size(); k++)
        printf("%s  %s  %s  %s  %s  %s  %s\n",
               padDisp(rows[k].name, 10).c_str(), padDisp(rows[k].note, 22).c_str(),
               padDisp(to_string(cmpAll[k]), 12).c_str(), padDisp(to_string(movAll[k]), 12).c_str(),
               padDisp(to_string(upAll[k]), 14).c_str(), padDisp(to_string(downAll[k]), 14).c_str(),
               padDisp(ans[k] == ans[gold] ? "同正解" : "✗ 不同", 8).c_str());

    bool allSame = true;
    for (auto& s : ans) allSame &= (s == ans[gold]);
    printf("\n★ 这 %d 种写法的答案%s。\n", (int)rows.size(), allSame ? "**完全一样**" : "有不一样的");
    printf("  —— 所以「swapHeap 比正解多搬了多少」这件事，对拍**一个字都看不见**。\n");
    if (nPush > 0)
        printf("★ log2(%d) = %.2f；对照上面 fast 那一行的「其中下沉比较 ÷ 删除次数」。\n",
               nPush, log2((double)nPush));
    return 0;
}

// ★ 建堆：一个个 push 是 O(n log n)，自底向上只要 O(n) —— 而且这条 O(n) 也**证得死死的**
//
// ============ 两种建法 ============
//
//   ① 一个个 push：把 n 个数依次插进空堆，每次上浮。
//      最坏 Σ log i = O(n log n)。
//   ② ★ 自底向上：把 n 个数原样倒进数组，然后 **从 n/2 往 1 倒着 down 一遍**。
//      for (int i = n / 2; i >= 1; i--) down(i);
//      为什么从 n/2 开始：下标 > n/2 的格子没有儿子，它们本来就是合法的堆（一个点的树）。
//      为什么**倒着**：down(i) 要求它的两棵子树已经是堆了 ——
//      「依赖谁，就先填谁」，第 21、26、27 章那句话在这里第八次登场。
//
// ============ ② 为什么是 O(n)：一行级数 ============
//
//   高度为 h 的点最多 ⌈n / 2^(h+1)⌉ 个，每个最多往下走 h 层，于是总层数
//
//       Σ_{h≥0} h · n / 2^(h+1)  =  (n/2) · Σ_{h≥0} h / 2^h  =  (n/2) · 2  =  n
//
//   （Σ h/2^h = 2 是那个经典的级数：1/2 + 2/4 + 3/8 + … = 2。）
//   每层最多 2 次比较 ⇒ **比较次数 ≤ 2n**。
//
//   ★ 直觉上的那句话更好记：**一半的点在最后一层，它们一步都不用走**；
//     真正要走 log n 层的只有根那一个点。**「大多数点很矮」才是 O(n) 的来源。**
//
// ============ ⚠ 这一节最该记住的一件事 ============
//
//   ★ 两种建法造出来的**数组通常不一样**（下面会逐格打出来给你看），
//     可它们都是合法的小根堆，**堆排序倒出来的结果一模一样** ——
//     ⚠ 于是「用了哪种建法」这件事，对拍**一个字都看不见**（第 36 章那个第四盲区）。
//     要看见差别，只能数次数。
//
// 用法：./build      < 数据      打印对比（n ≤ 30 时连两个数组一起打出来）
//       ./build csv  < 数据      一行一种建法：名字,比较次数,移动次数,堆排序结果的哈希
// 输入：第一行 n，第二行 n 个整数（用 ./genArr n 形状 造）。

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

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

struct Heap {
    vector<long long> h;                       // h[1..sz]
    int sz = 0;
    long long cmp = 0, mov = 0;

    void reset(int cap) { h.assign(cap + 2, 0); sz = 0; cmp = 0; mov = 0; }

    void up(int i) {
        long long x = h[i];
        while (i > 1) {
            cmp++;
            if (!(h[i >> 1] > x)) break;
            h[i] = h[i >> 1]; mov++; i >>= 1;
        }
        h[i] = x; mov++;
    }
    void down(int i) {
        long long x = h[i];
        while ((i << 1) <= sz) {
            int c = i << 1;
            if (c < sz) { cmp++; if (h[c + 1] < h[c]) c++; }
            cmp++;
            if (h[c] >= x) break;
            h[i] = h[c]; mov++; i = c;
        }
        h[i] = x; mov++;
    }

    /** ① 一个个 push */
    void buildByPush(const vector<long long>& a) {
        reset((int)a.size());
        for (long long x : a) { h[++sz] = x; mov++; up(sz); }
    }
    /** ② ★ 自底向上：先原样倒进去，再从 n/2 倒着 down */
    void buildHeapify(const vector<long long>& a) {
        reset((int)a.size());
        for (long long x : a) { h[++sz] = x; mov++; }
        for (int i = sz / 2; i >= 1; i--) down(i);
    }

    /** 堆排序：一个个倒出来（★ 这一段的开销不计进上面那两个计数器） */
    vector<long long> drain() const {
        Heap t = *this;
        vector<long long> r;
        while (t.sz) { r.push_back(t.h[1]); t.h[1] = t.h[t.sz--]; if (t.sz) t.down(1); }
        return r;
    }
};

static string join(const vector<long long>& v, int limit) {
    string s;
    for (int i = 0; i < (int)v.size() && i < limit; i++) { if (i) s += ' '; s += to_string(v[i]); }
    if ((int)v.size() > limit) s += " …";
    return s;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    Heap p, q;
    p.buildByPush(a);
    q.buildHeapify(a);

    vector<long long> sp = p.drain(), sq = q.drain();
    bool sameArray = true;
    for (int i = 1; i <= n; i++) sameArray &= (p.h[i] == q.h[i]);
    bool sameSorted = (sp == sq);

    if (argc > 1 && string(argv[1]) == "csv") {
        printf("push,%lld,%lld\n", p.cmp, p.mov);
        printf("heapify,%lld,%lld\n", q.cmp, q.mov);
        printf("same,%d,%d\n", sameArray ? 1 : 0, sameSorted ? 1 : 0);
        return 0;
    }

    printf("n = %d\n\n", n);
    printf("%s  %s  %s  %s\n", padDisp("建法", 10).c_str(), padDisp("比较次数", 12).c_str(),
           padDisp("移动次数", 12).c_str(), padDisp("比较 ÷ n", 12).c_str());
    printf("%s  %s  %s  %s\n", padDisp("一个个 push", 10).c_str(), padDisp(to_string(p.cmp), 12).c_str(),
           padDisp(to_string(p.mov), 12).c_str(), padDisp(to_string((double)p.cmp / n).substr(0, 5), 12).c_str());
    printf("%s  %s  %s  %s\n", padDisp("★ 自底向上", 10).c_str(), padDisp(to_string(q.cmp), 12).c_str(),
           padDisp(to_string(q.mov), 12).c_str(), padDisp(to_string((double)q.cmp / n).substr(0, 5), 12).c_str());
    printf("\nlog2(%d) = %.2f\n", n, log2((double)max(n, 1)));

    if (n <= 30) {
        printf("\n一个个 push 建出来的数组：  %s\n", join(vector<long long>(p.h.begin() + 1, p.h.begin() + 1 + n), 30).c_str());
        printf("★ 自底向上建出来的数组：    %s\n", join(vector<long long>(q.h.begin() + 1, q.h.begin() + 1 + n), 30).c_str());
    }
    printf("\n两个数组%s；堆排序倒出来的结果%s。\n",
           sameArray ? "**完全相同**" : "★ **不一样**（都是合法的小根堆，但长得不同）",
           sameSorted ? "**完全相同**" : "✗ 不同（那就有一份错了）");
    printf("  —— 所以「用了哪种建法」对拍看不见，只有比较次数看得见。\n");
    return 0;
}

// ★ 还第 12 章的账：第 k 小，用堆再做一遍
//
// 第 12 章给了两种解法：排序 O(n log n)、快速选择平均 O(n)，
// 并且在章末留了一句「还有别的做法，等讲完堆再回来」。这就是那一份。
//
// ============ 做法：维护一个大小为 k 的**大根堆** ============
//
//   扫过去，堆里始终装着「到目前为止最小的那 k 个数」：
//     · 堆里不足 k 个 → 直接放进去；
//     · 已经有 k 个 → 拿新来的 x 和**堆顶**（这 k 个里最大的那个）比：
//       x 更小就把堆顶扔掉、把 x 放进来；否则 x 连前 k 名都进不去，直接丢。
//   扫完之后，堆里正好是最小的 k 个数，而**堆顶就是它们里最大的** —— 也就是第 k 小。
//
//   ⚠ 要的是**第 k 小**，用的却是**大根堆** —— 这一步是最容易想反的。
//     记法：**堆顶是「守门员」**，它盯着的是「目前排第 k 名的那个」，
//     所以门口站的必须是这 k 个里最大的那一个。
//
// 复杂度 O(n log k)。
//
// ============ ★ 它凭什么值得单独存在（三种解法的真正分工）============
//
//   · 排序 O(n log n)：写起来最短，n 不大时怎么都够用。
//   · 快速选择平均 O(n)：**渐进最快**，但它要**把整个数组抓在手里反复划分**。
//   · 堆 O(n log k)：渐进上比快速选择差一个 log，可它有两样别人没有的东西 ——
//     ① **只占 O(k) 的内存**（k 远小于 n 时差距是数量级的）；
//     ② ★ **数据可以一个个来、来了就扔**（数据流 / 在线）：
//        它从头到尾只需要看每个数**一眼**，不需要回头。
//        快速选择做不到这件事 —— 它必须能反复访问整个数组。
//
//   > ★ **「哪个更快」不是唯一的问题，「它需要什么条件」同样是问题。**
//     （第 24 章那条「二进制拆分 vs 单调队列，交叉点在 k ≈ 100」的同款分寸。）
//
// ★ 输入输出和第 12 章的 selectBrute.cpp / selectFast.cpp **完全一样**，
//   所以这三份可以直接互相对拍（check:viz 里就是这么钉的）——
//   ⚠ 而且这是**跨章节**对拍：第 12 章的生成器一个字都没改就拿来用了。
//
// 输入：第一行 n k，第二行 n 个整数。
// 输出：从小到大数，第 k 个是多少。

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

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    if (n <= 0 || k < 1 || k > n) { cout << 0 << "\n"; return 0; }

    priority_queue<long long> q;               // ★ 默认就是大根堆，这里要的正是它
    long long pushes = 0;                      // 有多少个数真的进过堆（给 ./heapKth cnt 用）

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;                              // ★ 每个数只看一眼，看完就可以扔
        if ((int)q.size() < k) { q.push(x); pushes++; }
        else if (x < q.top()) { q.pop(); q.push(x); pushes++; }
    }

    if (argc > 1 && string(argv[1]) == "cnt") {
        // 「入堆次数」是可复现的尺子（秒数不是）——正文里那张表用它说明
        // ★ 「x < 堆顶」这件事随着扫描越来越难发生，所以入堆次数远小于 n。
        printf("n = %d, k = %d, 入堆次数 = %lld\n", n, k, pushes);
        return 0;
    }

    cout << q.top() << "\n";                   // 堆顶 = 最小的 k 个里最大的 = 第 k 小
    return 0;
}

// 正解 —— 手写小根堆（完全二叉树塞进数组，上浮 / 下沉各 O(log n)）
//
// ============ 这一章的 log，是**证得死死的** ============
//
// 第 36 章那个 O(α(n)) 只能给结论 + 实测（完整证明超出这本书的范围）。
// 这一章正好反过来：两句话就证完了，而且**每一步都能在数组上数出来**。
//
//   ① 堆是一棵**完全二叉树**：除了最后一层，每层都填满，最后一层靠左。
//      于是它有多高？第 0 层 1 个、第 1 层 2 个、第 2 层 4 个……
//      前 h 层一共 2^h − 1 个点，所以 n 个点的完全二叉树高度就是 **⌊log₂ n⌋**。
//      —— 不是估的，是**数出来的**。
//   ② 上浮只往上走（每次 i → i/2），下沉只往下走（每次 i → 2i 或 2i+1），
//      两者走的都是**一条根到叶的路** —— 长度不超过树高。
//
//   ⇒ 每次 push / pop 都是 O(log n)。n = 2×10⁵ 时这个数只有 **17**。
//
// ============ 数组下标：为什么从 1 开始 ============
//
//   下标 i 的两个儿子是 2i 和 2i+1，爸爸是 i/2（整除）。
//   ⚠ 从 0 开始的话就得写成 2i+1 / 2i+2 和 (i−1)/2，能用但难记 ——
//     这一章统一 1 基（和区间类题目那条约定同源：下标从 1 开始，公式才干净）。
//
// ============ 为什么用「空穴法」而不是一路 swap ============
//
//   一次 swap 是三次赋值（tmp = a; a = b; b = tmp）。
//   可上浮 / 下沉的路上，那个被挪动的元素**最后总要落在某一格**，中间那些位置它只是路过。
//   所以正确的写法是：先把它抱在手上（int x = a[i]），沿路只把别人往它腾出来的空穴里搬，
//   最后再把它放下 —— **每层只有一次赋值，不是三次**。
//
//   ★ 这个改动**不影响任何一个答案**，只影响移动次数（实测差三倍，见 count.cpp）。
//     ⚠ 也就是说：对拍在它身上一辈子抓不到 —— 第 36 章那个「第四个盲区」在这一章又见了一次。
//
// 复杂度 O(n log n)。

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

const int MAXN = 200005;
long long a[MAXN];                             // ★ a[1..sz] 才是堆，a[0] 空着不用
int sz = 0;

/** 上浮：a[i] 比爸爸小就往上，直到爸爸不比它大（或者它已经是根） */
void up(int i) {
    long long x = a[i];                        // 抱在手上
    while (i > 1 && a[i >> 1] > x) {
        a[i] = a[i >> 1];                      // 爸爸落到空穴里
        i >>= 1;
    }
    a[i] = x;                                  // 放下
}

/** 下沉：a[i] 比儿子大就往下，★ 两个儿子里要挑**小的**那个换 */
void down(int i) {
    long long x = a[i];
    while ((i << 1) <= sz) {
        int c = i << 1;
        if (c < sz && a[c + 1] < a[c]) c++;    // ⚠ c < sz 才有右儿子（c == sz 时只有左儿子）
        if (a[c] >= x) break;                  // 已经就位，不用再往下了
        a[i] = a[c];
        i = c;
    }
    a[i] = x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    string out;
    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            long long x;
            cin >> x;
            a[++sz] = x;                       // 先放到最后一格（完全二叉树的下一个空位）
            up(sz);                            // 再上浮到该去的地方
        } else if (op == 2) {
            if (sz == 0) out += "E\n";
            else { out += to_string(a[1]); out += '\n'; }   // 堆顶就是最小值，O(1)
        } else {
            if (sz == 0) continue;
            a[1] = a[sz--];                    // ★ 拿最后一格填到根上（完全二叉树的形状不能破）
            if (sz) down(1);                   // 再把它沉到该去的地方
        }
    }

    // ★ 最后那一行：把堆里剩下的全部按从小到大倒出来 —— 就是一次堆排序
    vector<long long> rest;
    while (sz) {
        rest.push_back(a[1]);
        a[1] = a[sz--];
        if (sz) down(1);
    }
    if (rest.empty()) out += "-\n";
    else {
        for (size_t i = 0; i < rest.size(); i++) {
            if (i) out += ' ';
            out += to_string(rest[i]);
        }
        out += '\n';
    }

    cout << out;
    return 0;
}