Tsm

// TSM.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <iterator>
#include <vector>

#define NMAX 1000001


class InParser {
public:
    InParser (const char* file_name) {
        input_file.open (file_name, std::ios::in);
        input_file.sync_with_stdio (false);
        index = 0;
        input_file.read (buffer, SIZE);
    }

    InParser& operator >> (int& n) {
        for (; buffer[index] < '0' || buffer[index] > '9'; inc ());
        n = 0;

        for (; '0' <= buffer[index] && buffer[index] <= '9'; inc ())
            n = n * 10 + buffer[index] - '0';

        return *this;
    }

    ~InParser () {
        input_file.close ();
    }

private:
    std::fstream input_file;
    static const int SIZE = 0x400000; ///4MB
    char buffer[SIZE];
    int index = 0;

    inline void inc () {
        if (++index == SIZE)
            index = 0, input_file.read (buffer, SIZE);
    }
};

class OutParser {
public:
    OutParser (const char* file_name) {
        output_file.open (file_name, std::ios::out);
        output_file.sync_with_stdio (false);
        index = 0;
    }

    OutParser& operator << (int target) {
        aux = 0;
        n = target;
        if (!n)
            nr[aux ++] = '0';
        for (; n; n /= 10)
            nr[aux ++] = n % 10 + '0';
        for (; aux; inc ())
            buffer[index] = nr[-- aux];

        return *this;
    }

    OutParser& operator << (const char* target) {
        aux = 0;
        while (target[aux])
            buffer[index] = target[aux ++], inc ();

        return *this;
    }

    ~OutParser () {
        output_file.write (buffer, index);
        output_file.close ();
    }

private:
    std::fstream output_file;
    static const int SIZE = 0x200000; ///2MB
    int index = 0, aux = 0, n = 0;
    char buffer[SIZE], nr[24];

    inline void inc () {
        if (++index == SIZE)
            index = 0, output_file.write (buffer, SIZE);
    }
};

InParser fin ("tsm.in");
OutParser fout ("tsm.out");

int n, task, val, x;
std::multiset <int> Heap;
std::vector <int> BIT (NMAX);
/*std::map <int, int> Hash;
std::set <int>::iterator it;*/


inline void Update (int index, int val) {
    while (index < NMAX)
        BIT[index] += val, index += index & (- index);
}

inline int Query (int index) {
    int sum = 0;
    while (index > 0)
        sum += BIT[index], index -= index & (- index);

    return sum;
}

inline int Kth_smallest (int k) {
    auto it = Heap.end(); -- it;
    int st = 1, dr = *it; //fout << "\t\t" << st << " " << dr << ": ";
    while (st < dr) {
        int mid = (st + dr) / 2;
        if (k <= Query (mid))
            dr = mid;
        else st = mid + 1;
        //fout << st << " -> ";
    }
    //fout << "\n";

    return st;
}


int main () {
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> task;
        switch (task) {
        case 1: {
            fin >> val;
            if (Heap.find (val) == Heap.end ())
                Update (val, 1);
            Heap.insert (val);
        }
                break;
        case 2: {
            fin >> val;
            fout << (x = Kth_smallest (val)) << "\n";
        }
                break;
        case 3: {
            fout << *(Heap.begin ()) << "\n";
        }
                break;
        case 4: {
            Heap.erase (Heap.lower_bound (x));
            if (Heap.find(x) == Heap.end())
                Update (x, - 1);
        }
                break;
        }
        /*
        fout << "\n\t";
        for (auto it : Heap)
            fout << it << " " << Query (it) << " | ";
        fout << "\n";
        */
    }

    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started:
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file