동적으로 정수가 추가되는 상황에서 현재까지 입력된 정수들의 중앙값(Median)을 효율적으로 구하고 싶습니다.
중앙값은 자료를 크기순으로 정렬했을 때 가장 중앙에 위치하는 값을 의미합니다.
명령은 다음과 같이 두 종류로 주어집니다.
- I x: 정수 $x$를 리스트에 삽입합니다.
- M: 현재 리스트에 저장된 모든 정수들 중 중앙값을 출력합니다. 단, 현재 저장된 원소의 개수가 짝수 개인 경우에는 중앙에 있는 두 원소 중 더 작은 값을 중앙값으로 선택합니다. (예: [1, 2, 3, 4] 의 중앙값은 2)
명령어 리스트가 주어졌을 때, 각 M 명령어에 대해 중앙값을 출력하는 프로그램을 작성하십시오.

[제약 조건]
• 명령 수 $Q$: $1 \le Q \le 5{,}000$
• 삽입 정수 $x$: $-10^9 \le x \le 10^9$

첫째 줄에 명령어의 개수 $Q$가 주어집니다. ($1 \le Q \le 5000$)
둘째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 명령어 I x (삽입할 정수 $x$의 범위는 $-10^9 \le x \le 10^9$) 또는 M이 주어집니다.
첫 M 명령어가 나오기 전에 최소 하나 이상의 정수가 삽입되는 것이 보장됩니다.

명령어 M이 주어질 때마다 현재까지 저장된 수들의 중앙값을 줄바꿈하여 한 줄씩 출력합니다.

6
I 5
I 3
M
I 7
I 2
M

3
3