Description

Given an integer sequence of $N$ elements, there are two operations:

• $\texttt{1 add }\textit{a}$: Append an integer $a$ to the end of the sequence, forming a sequence of length $N + 1$.
• $\texttt{2 mid}$: Output the median of the current sequence.

The median is the number that lies in the middle after sorting the sequence in non-decreasing order. If the sequence length is even, it is the smaller of the two middle numbers.

Example 1: $[1, 2, 13, 14, 15, 16]$ has median $13$.
Example 2: $[1, 3, 5, 7, 10, 11, 17]$ has median $7$.
Example 3: $[1, 1, 1, 2, 3]$ has median $1$.

Input Format

The first line contains the initial sequence length $N$.
The second line contains $N$ integers, representing the sequence, separated by spaces.
The third line contains the number of operations $M$, meaning you will perform $M$ operations.
Then follow $M$ lines, each in the format described above.

Output Format

For each $\verb!mid!$ operation, output the value of the median.

6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid

5
13

Hint

Constraints

• For $30\%$ of the testdata, $1 \le N \le 10{,}000$, $0 \le M \le 1{,}000$.
• For $100\%$ of the testdata, $1 \le N \le 100{,}000$, $0 \le M \le 10{,}000$.

The absolute value of each integer in the sequence does not exceed $10^9$, and numbers in the sequence may repeat.

Translated by ChatGPT 5