Delete the X-th smallest number

Maintain a multiset under insertions and queries that report and delete the X-th smallest element, with values and query count up to 2e6.

Medium6Segment treeBinary searchArrayImplementationNo attempts yetTime limit2sMemory limit512 MB

Description

Examples1

Problem

You maintain a data structure S that holds natural numbers. S starts empty, and the same number can be inserted more than once. Inserting the same value twice leaves S with two elements.

Process the following two query types in the order they are given.

Type 1: insert the natural number $X$ into S.

Type 2: sort the elements of S in increasing order, print the $X$ -th one, and remove that single element from S.

Input

The first line contains the number of queries $N$ . ( $1 \le N \le 2 \times 10^6$ )

Each of the next $N$ lines contains one query as two integers $T$ $X$ .

If $T$ is 1, then $X$ is the value to insert into S. ( $1 \le X \le 2 \times 10^6$ )

If $T$ is 2, then $X$ says which smallest element to remove. S is guaranteed to hold at least $X$ elements at that moment.

Output

For each type 2 query, print the answer on its own line, in the order the queries are given. If there is no type 2 query, print nothing.