struct Heap
{
    vector<int> v, heap_v, pos;  ///v - значения, heap_v - куча индексов, pos - позиции в куче
    int n = 0;
    bool flag_; ///определитель кучи на максимум или минимум

    explicit Heap(bool flag){
        heap_v.resize(1);
        heap_v[0] = -1;
        flag_ = flag;
    }

    void heap_swap(int i, int j) {
        swap(pos[heap_v[i]], pos[heap_v[j]]);
        swap(heap_v[i], heap_v[j]);
    }

    bool is_valid_node(int i) {
        return i > 0 && i <= n;
    }

    bool is_valid_parent(int p, int c) {
        return is_valid_node(p) && is_valid_node(c) && (v[heap_v[p]] < v[heap_v[c]])^flag_;
    }

    void siftUp(int i)
    {
        int p = i / 2;
        while (is_valid_node(p) && !is_valid_parent(p, i)) {
            heap_swap(i, p);
            i = p;
            p = i / 2;
        }
    }

    void siftDown(int i) {
        int l = 2*i;
        while (l <= n){
            if (is_valid_parent(l+1, l)) l++;
            if (is_valid_parent(i, l)) break;
            else {
                heap_swap(i, l);
                i = l;
                l = 2*i;
            }
        }
    }

    void Insert(int new_el) {
        v.push_back(new_el);
        pos.push_back(n+1);
        heap_v.push_back(v.size()-1);
        n++;
        siftUp(n);
    }

    void Del(int i) {
        ///i = pos[i];
        swap(heap_v[i], heap_v[n]);

        heap_v.pop_back();
        n--;
        if(i <= n) {
            pos[heap_v[i]] = i;
            siftUp(i);
            siftDown(i);
        }
    }

    int Get(int i) { return v[heap_v[i]];}
};