rt.

我的做法如下：

#include <bits/stdc++.h>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

char buf[1 << 21], *p1 = buf, *p2 = buf;

using namespace std;

const int N = 1e5 + 7; 

inline
int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' or ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ '0');
		ch = getchar();
	}
	return x * f;
}

struct data {
	int l, r, sz;
}tr[N << 4];

int n, a[N], cnt, key, rk[N], id[N], rt[N];

bool cmp(const int &x, const int &y) {
	return a[x] < a[y];
}

void build(int l, int r, int &pos) {
	tr[++cnt] = tr[pos];
	pos = cnt;
	tr[cnt].sz++;
	if (l == r) return ;
	int mid = l + r >> 1;
	if (key <= mid) build(l, mid, tr[cnt].l);
	else build(mid + 1, r, tr[cnt].r);
}

int query(int l, int r, int x, int y, int k) {
	if (l == r) return l;
	int mid = l + r >> 1, sz = tr[tr[y].l].sz - tr[tr[x].l].sz;
	if (k <= sz) return query(l, mid, tr[x].l, tr[y].l, k);
	else return query(mid + 1, r, tr[x].r, tr[y].r, k - sz);
} 

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		id[i] = i;
	}
	sort(id + 1, id + 1 + n, cmp);
	for (int i = 1; i <= n; i++) rk[id[i]] = i;
	for (int i = 1; i <= n; i++) {
		rt[i] = rt[i - 1];
		key = rk[i];
		build(1, n, rt[i]);
	}
	for (int i = 2; i <= n; i++) printf ("%d ", a[id[query(1, n, rt[0], rt[i], 2)]]);
	return 0;
}

赛后写的，不确定正确性。