14031403 SUSTech Online Judge
Problem 1403 --The k-th largest number

1403: The k-th largest number

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 470  Solved: 162
[Submit][Status][Web Board]

Description

    There is a sequence, there are two operations, for operation 1, add one number into the sequence, for operation 2, find the k-th largest number and delete all the number current in the sequence bigger than it.  

Input

The first line contains an Integer n\((2\leq n\leq 10^6)\), representing the number of the operations.

The next n line contains two numbers. The format is (1, x) or (2, k)

If it is (1, x), then add the x into the sequence.

If it is (2, k), find the k-th largest number and delete all the number current in the sequence bigger than it.

Note that, it is guarantee that when operate the operation 2, there are at least k numbers in the sequence. In the sequence, there are no two same numbers.

Output

For each line, output the operation 2 result(Output the k-th largest number).

Sample Input

5
1 2
1 3
2 2
1 4
2 1

Sample Output

2
4

HINT

Source

 

[Submit][Status]