堆

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int x;
    priority_queue<int, vector<int>, less<int>> a;
    priority_queue<int, vector<int>, greater<int>> b;
    auto check = [&](){
        int k = a.top();
        a.pop();
        return k;
    };
    auto adjust = [&]() {
        int A = a.size(), B = b.size();
        int len = (A + B + 1) / 2;
        if (A > len) {
            b.emplace(a.top()); a.pop();
        } else if (A < len) {
            a.emplace(b.top()); b.pop();
        }
    };
    auto push = [&](int k) {
        if (a.empty() || k <= a.top()) {
            a.emplace(k);
        } else {
            b.emplace(k);
        }
    };
    while (cin >> x) {
        if (x == 0) {
            break;
        }
        if (x == -1) {
            cout << check() << "\n";
        } else {
            push(x);
        }
        adjust();
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}