实测 $O(n\log_2 n)$ 可过。

评测记录

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#define R register
#define N 3000005
char Buf[1 << 21], *S(Buf), *T(Buf);
#define getchar() (S == T && (T = (S = Buf) + fread(Buf, 1, 1 << 21, stdin), S == T) ? EOF : *S++)
inline int input() {
    R int x(0);
    R char c(getchar());
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
int n, tot, a[N], c[N], Ans[N];
struct Data {
	int pos, val;
	inline Data(int P = 0, int V = 0) : pos(P), val(V) {}
	inline bool operator < (const Data &b) { return val > b.val; }
};
inline int min(int a, int b) { return a < b ? a : b; }
Data b[N];
inline int Get(int x) {
	R int ret(N);
	for (R int i(x); i; i -= i & -i) ret = min(c[i], ret);
	return ret;
}
inline void Update(int x, int k) {
	for (R int i(x); i <= tot; i += i & -i) c[i] = min(c[i], k);
}
int main() {
	n = input();
	for (R int i(1); i <= n; ++i) b[i] = Data(i, input());
	std :: sort(b + 1, b + n + 1);
	for (R int i(1); i <= n; ++i) a[b[i].pos] = (tot += (b[i].val != b[i - 1].val));
	for (R int i(1); i <= n; ++i) c[i] = N;
	for (R int i(n); i >= 1; --i) Ans[i] = Get(a[i] - 1), Update(a[i], i);
	for (R int i(1); i <= n; ++i) printf("%d ", Ans[i] == N ? 0 : Ans[i]);
    return 0; 
}

可能要将时限缩小到 $500\text{ms}$ 左右。