Description

GY bought a batch of gemstones and put them in a warehouse. One day, GY decided to count them, so he took out $m$ gemstones and put them into a gemstone management system. Each gemstone $i$ has a value $v_i$. He hopes you can write a program to find the $n$-th most valuable gemstone in descending order. However, there is a problem: he carelessly left some gemstones in the warehouse, and he may add them to the current system. The number of such gemstones is small. He is sorry, but he still hopes your system will work.

Input Format

The first line contains two integers $m, q$, the number of gemstones already taken out and the number of following queries or insertions.

The second line contains $m$ integers, the values of these $m$ gemstones.

Each of the following $q$ lines contains two integers $c, n$.

If $c = 1$ (query), output the current $n$-th most valuable gemstone.

If $c = 2$ (insertion), insert a gemstone with value $n$ into the system.

Output Format

For each case with $c = 1$ (query), output the value $v_i$ of the current $n$-th most valuable gemstone.

5 3
1 3 2 5 6
1 3
2 4
1 6

3
1

Hint

• For $50\%$ of the testdata, there is no case with $c = 2$.
• For $100\%$ of the testdata, $m \leq 100000$, the number of cases with $c = 2$ does not exceed $10000$, $q \leq 30000$, $0 \leq v_i < 2^{31}$.

Translated by ChatGPT 5