ORDERSET (Segment Tree)

/*
Khởi tạo toàn bộ cây có giá trị bằng 0.
Tại mỗi lá, nếu lá đó trong S có giá trị bằng thứ tự của lá đó, ta sẽ cập nhập lá đó bằng 1, và cập nhật lại toàn bộ cây.
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 200001;
int n, x;
char s[N];
int a[N], b[N], pos[N], c[N];
int st[N * 5];

void build(int id, int l, int r)
{
    if (l == r) {
        pos[l] = id;
        st[id] = 0;
        return;
    }

    int mid = (l+r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    st[id] = st[id*2] + st[id*2+1];
    st[id] = 0;
}

int get(int id, int l, int r, int u, int v)
{
    if (v < l || u > r)
        return 0;
    if (u <= l && r <= v)
        return st[id];

    int mid = (l+r) / 2;
    int t1 = get(id*2, l, mid, u, v);
    int t2 = get(id*2+1, mid + 1, r, u, v);

    return t1 + t2;
}

void tinh() {
    for (int i = 1; i <= n; i++)
    {
        //Khi nhập vào lệnh INSERT(S,x)
        if (s[i] == 'I') {
            int id = pos[b[i]];
            st[id] = 1;

            while (id/2 > 0) {
                id = id / 2;
                st[id] = st[2*id] + st[2*id+1];
            }
        }else

        //Khi nhập vào lệnh DELETE(S,x)
        if (s[i] == 'D') {
            int id = pos[b[i]];
            st[id] = 0;

            while (id/2 > 0) {
                id = id / 2;
                st[id] = st[2*id] + st[2*id+1];
            }
        } else

        //Khi nhập vào lệnh K-TH(S), cần phải trả về số bé thứ k, ta sử dụng chặt nhị phân để tìm
        if (s[i] == 'K') {
            if (a[i] > get(1, 1, n, 1, n)) {
                cout << "invalid" << '\n';
                continue;
            }

            int lo = 0, hi = n;
            while (hi - lo > 1) {
                int mid = (lo+hi) / 2;
                if (a[i] <= get(1, 1, n, 1, mid))
                    hi = mid;
                else lo = mid;
            }

            cout << c[hi] << '\n';
        } else

        //Khi nhập vào lệnh COUNT(S,x) – đếm số lượng số thuộc S bé hơn x, ta tính tổng tất cả các lá từ 1 tới x-1
        cout << get(1, 1, n, 1, b[i]-1) << '\n';
    }

}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> a[i];
        c[i] = a[i];
    }

    sort(c + 1, c + n + 1);

    for (int i = 1; i <= n; i++)
        b[i] = lower_bound(c+1, c+n+1, a[i]) - c;

    build(1, 1, n);

    tinh();

    return 0;

}



/*
Bạn cần quản lý một tập hợp động các số, hỗ trợ hai thao tác cơ bản:
INSERT(S,x): nếu x không thuộc S, thêm x vào S
DELETE(S,x): nếu x thuộc S, xóa x khỏi S

Hai loại truy vấn:
K-TH(S) : trả về số bé thứ k của S
COUNT(S,x): đếm số lượng số thuộc S bé hơn x

Với mỗi truy vấn, in ra kết quả tương ứng trên một dòng. Với truy vấn K-TH, nếu k lớn hơn số phần tử của S, in ra ‘invalid’.

8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2

Kết quả
1
2
2
*/