Black Box

Black Box represents a primitive database that can store an array of integers and has a special variable $i$. Initially, the Black Box is empty and $i$ is $0$. The Black Box processes a sequence of commands (transactions) of two types:

ADD($x$): Adds element $x$ to the Black Box.

GET: Increments $i$ by $1$ and returns the $i$-th minimum of all integers currently in the Black Box.

Remember, the $i$-th minimum is the number at position $i$ after sorting all Black Box elements in non-decreasing order.

You need to design an efficient algorithm to process a given sequence of transactions. The maximum number of ADD and GET transactions is $30000$ each.

The sequence of transactions is described by two integer arrays:

1. A(1), A(2), \ldots, A(m): a sequence of integers to be added to the Black Box. Each $A$ is an integer with |A| \leq 2\ 000\ 000\ 000, m \leq 30000. For example: A = (3, 1, -4, 2, 8, -1000, 2).

2. u(1), u(2), \ldots, u(n): a sequence indicating how many elements are currently in the Black Box for the $1$st, $2$nd, ..., $n$-th GET operation. For the example above: u = (1, 2, 6, 6).

It is assumed that the sequence u(1), u(2), \ldots, u(n) is sorted in non-decreasing order, n \leq m, and for each $p$ (1 \leq p \leq n), the inequality p \leq u(p) \leq m holds. This means that for the $p$-th element of the $u$ sequence, the $p$-th minimum is extracted from the set A(1), A(2), \ldots, A(u(p)).