문제 111
중앙값과 거리 합
처음에 비어 있는 정수 다중집합 $S$가 있다. $S$가 비어 있지 않을 때, 원소를 오름차순으로 나열한 수열의 $\lceil \lvert S\rvert/2\rceil$번째 값을 아래 중앙값이라고 한다. 중복 원소도 각각 센다. 다음 $Q$개의 명령을 순서대로 처리해 보자.
- $0\ x$: $x$를 하나 추가한다.
- $1\ x$: $x$를 하나 삭제한다. 없다면 무시한다.
- $2$: 아래 중앙값을 구한다.
- $3$: 아래 중앙값 $m$에 대해 $\sum_{a\in S}\lvert a-m\rvert$을 구한다.
- $4$: 원소의 개수를 구한다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 본문에서 설명한 형식의 명령이 주어진다. 각 명령의 정수는 공백으로 구분되어 주어진다. $(-2^{63} \le x \le 2^{63}-1)$
출력
$2$번부터 $4$번 명령의 답을 명령이 주어진 순서대로 한 줄에 하나씩 출력한다.
$S$가 비어 있다면 $2$번 명령은 EMPTY를, $3$번 명령은 $0$을 출력한다.
예제 입력 1
12 2 0 1 0 7 2 3 0 7 2 3 1 7 4 2 3
예제 출력 1
EMPTY 1 6 7 6 2 1 6