Tập hợp thứ tự (Order statistic set)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì một tập hợp động $S$ gồm các số nguyên, ban đầu rỗng. Có $Q$ thao tác:

• I x: nếu $x\notin S$ thì chèn $x$.
• D x: nếu $x\in S$ thì xóa $x$.
• K k: in phần tử nhỏ thứ $k$ của $S$.
• C x: in số phần tử của $S$ nhỏ hơn $x$.

Nếu truy vấn K k có $k>|S|$, in invalid.

Input

Dòng đầu chứa $Q$.

$Q$ dòng tiếp theo chứa một thao tác. Với tham số giá trị $x$, $|x|\le10^9$. Với tham số thứ hạng $k$, $1\le k\le10^9$.

Output

In đáp án của mỗi truy vấn K hoặc C trên một dòng.

Subtask

• Subtask 1 — 20%: $1\le Q\le50$.
• Subtask 2 — 30%: $1\le Q\le5000$.
• Subtask 3 — 50%: $1\le Q\le2\cdot10^5$.

Ví dụ

Input

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

Output

1
2
2
invalid

Giải thích

Lệnh chèn -1 lần thứ hai không làm thay đổi tập. C 0 đếm đúng một phần tử là -1; sau khi xóa -1, truy vấn phần tử nhỏ thứ hai trở nên không hợp lệ.