再论中位数：离线+链表法

离线先得到整个序列，从最终开始倒推答案
每次删掉一个数要么对中位数没有影响，要么向左/右移动一个
为了确定要删除的元素在链表中的位置，使用map记录，重复删完更新
向左向右可以按照删除的元素相对于中位数的位置确定，具体分类见代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std ;

const int N = 10010 ;

int head, rnd, rid, n ;
int a[N], b[N], pre[N], suf[N] ;
vector <int> ans ;
map <int, int> ref ;
bool is_left = false ;

int main() {
	scanf("%d", &rnd) ;
	while (rnd--) {
		scanf("%d%d", &rid, &n) ;
		ans.clear() ;
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i] ;
		sort(b + 1, b + n + 1) ;
		for (int i = 1; i <= n; i++) ref[b[i]] = i ;
		for (int i = 1; i <= n; i++) pre[i] = i - 1, suf[i] = i + 1 ;
		pre[1] = suf[n] = 0 ;
		int mid = n / 2 + 1 ;
		ans.push_back(b[mid]) ;
		for (int i = n; i >= 1; i--) {
			int del = ref[a[i]] ;
			if (pre[del] && b[pre[del]] == b[del]) ref[a[i]] = pre[del] ;
			else if (suf[del] && b[suf[del]] == b[del]) ref[a[i]] = suf[del] ;
			if (i % 2 == 0) {
				if (is_left && del <= mid) mid = suf[mid] ;
				if (!is_left && del >= mid) mid = pre[mid] ;
				ans.push_back(b[mid]) ;
			} else {
				if (del == mid) mid = pre[mid], is_left = true ;
				else {
					if (del < mid) is_left = true ;
					else is_left = false ;
				}
			}
			suf[pre[del]] = suf[del] ;
			pre[suf[del]] = pre[del] ;
		}
		reverse(ans.begin(), ans.end()) ;
		printf("%d %d\n", rid, n / 2 + 1) ;
		for (int i = 0; i < ans.size(); i++) {
			printf("%d", ans[i]) ;
			if (i == ans.size() - 1) puts("") ;
			else if (i % 10 == 9) puts("") ;
			else printf(" ") ;
		}
	}
}