This problem can be solved using a multiset pair to store the current state of the sequence.

Whenever you push new value to the sequence, you can insert \(\{queryID + 2e9, value\}\) to the multiset. Therefore, new elements will be at the end of the multiset no matter what.

When you need to sort out the whole sequence, just keep checking the last pair in the multiset and replace it with \(\{value, value\}\). Then, the sorted elements will be in non-decreasing order and the element at the beginning of the set will be the answer for each 2nd type query.

Complexity: \(O(Q*log(2e9))\)

Submission: https://atcoder.jp/contests/abc217/submissions/25583472