离线先得到整个序列，从最终开始倒推答案
每次删掉一个数要么对中位数没有影响，要么向左/右移动一个
为了确定要删除的元素在链表中的位置，使用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(" ") ;
}
}
}