P3871 [TJOI2010] Median

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$.

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.

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

### 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