First of all, if you literally process the queries with an array, it will lead to TLE. This is because, for \(n\) elements, each query costs

• Query \(1\) : \(\mathrm{O}(1)\)
• Query \(2\) : \(\mathrm{O}(n)\)
• Query \(3\) : \(\mathrm{O}(n \log n)\)

time, so when you are given “\(\frac{Q}{2}\) number of Query \(1\), and then \(\frac{Q}{2}\) number of Query \(3\),” it will cost about \(\mathrm{O}(Q^2 \log Q)\) time complexity.

First, let us divide the array into two parts: sorted, and not sorted. Then the problem can be rephrased as follows.

There is an array \(A_1\) and a sorted array \(A_2\). Process the following queries.

• Query \(1\) : Append \(x\) to \(A_1\)
• Query \(2\) : If \(A_2\) is non-empty, output and remove the first element of \(A_2\); if empty, output and remove the first element of \(A_1\)
• Query \(3\) : Transfer all the elements in \(A_1\) to \(A_2\) and sort \(A_2\)

Here, Query \(1\) can be optimized, since they can be processed in an \(\mathrm{O}(1)\) by managing \(A_1\) with a queue instead of an array. The issue is Query \(3\).

Here, notice that the only information needed in the output Query \(2\) is the first element of \(A_1\) and \(A_2\). This means that the only information that \(A_2\) has to store is its minimum element.

Therefore, one can reduce the time complexity by managing \(A_2\)’s data with a priority queue. Specifically, we can construct the algorithm described below, so that we no longer need to sort every time.

Prepare a queue \(Q_1\) and a priority queue \(Q_2\) that enables us to obtain the minimum element in priority. Process the queries as follows.

• Query \(1\) : push \(x\) to \(Q_1\).
• Query \(2\) : perform either of the following two operations depending on whether \(Q_2\) is empty or not:
  • If \(Q_2\) is empty, output the first element of \(Q_1\) and pop it.
  • If \(Q_2\) is not empty, output the minimum element of \(Q_2\) and pop it.
• Query \(3\) : Transfer all the elements in \(Q_1\) to \(Q_2\).

Analysis is a bit complicated. Denoting the number of elements in queue by \(|Q|\), the worst time complexity per query is

• Query \(1\) : \(\mathrm{O}(1)\)
• Query \(2\) : \(\mathrm{O}(\log |Q_2|)\)
• Query \(3\) : \(\mathrm{O}(|Q_1| \log |Q_1 + Q_2|)\)

in which the time complexity of Query \(3\) looks bad, so it seems that there is no difference from the TLE algorithm above.

However, the overall time complexity of this algorithm is in fact \(\mathrm{O}(Q \log Q)\). This is why: the \(|Q_1|\) part of time complexity of Query \(3\) means the number of times that elements were pushed to \(Q_2\), but since the number of elements in this problem is \(Q\), so the number of elements added by Query \(3\) has the upper bound of \(\mathrm{O}(Q)\). Therefore, the total time complexity of Query \(3\) over all the queries is \(\mathrm{O}(Q \log Q)\).

An analysis of computational complexity over all queries like this is called amortized analysis. Also, the average complexity of queries like Query \(3\) is \(\mathrm{O}(\log Q)\). Such queries is said to have “amortized complexity of \(\mathrm{O}(\log Q)\).” Amortized complexity is used for analysis of many algorithms. One typical example is an addition of element (push_back) to a dynamic array (std::vector).

Therefore, the problem has been solved in a total of \(\mathrm{O}(Q \log Q)\) time.
Another way of solving this problem is to do binary search on Segment Tree.