Median Finder

Given an integer sequence with \(N\) elements, you have two types of operations:

• \(\texttt{1 add }a\) : Append an integer \(a\) to the end of the sequence, increasing its length by one.
• \(\texttt{2 mid}\) : Output the median of the current sequence.

The median is defined as the middle element after sorting the sequence in non-decreasing order. If the sequence has an even length, the median is the smaller one among the two middle elements. For example:

• Sequence: [1, 2, 13, 14, 15, 16] → Median: 13
• Sequence: [1, 3, 5, 7, 10, 11, 17] → Median: 7
• Sequence: [1, 1, 1, 2, 3] → Median: 1

inputFormat

The first line contains an integer \(Q\), the number of operations. Each of the following \(Q\) lines contains an operation in one of the following formats:

• "1 add a" — Append the integer \(a\) to the sequence.
• "2 mid" — Output the current median.

It is guaranteed that there is at least one "2 mid" operation in the input.

outputFormat

For each operation of type "2 mid", output the median of the current sequence on a new line.

sample

7
1 add 1
1 add 2
1 add 13
1 add 14
1 add 15
1 add 16
2 mid

13