感觉分情况讨论清楚就好啦， 不是很难写。

#include
     
      #define LL long long#define LD long double#define ull unsigned long long#define fi first#define se second#define mk make_pair#define PLL pair
      
       #define PLI pair
       
        #define PII pair
        
         #define SZ(x) ((int)x.size())#define ALL(x) (x).begin(), (x).end()#define fio ios::sync_with_stdio(false); cin.tie(0);using namespace std;const int N = 1e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 998244353;const double eps = 1e-8;const double PI = acos(-1);template
         
           inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}template
          
            inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}template
           
             inline bool chkmax(T& a, S b) { return a < b ? a = b, true : false;}template
            
              inline bool chkmin(T& a, S b) { return a > b ? a = b, true : false;}int n, a[N], pos[N], from[N], ans[N];bool ban[N];set
             
               segEnd;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1struct segmentTree { PII mx[N << 2]; void build(int *a, int l, int r, int rt) { if(l == r) { mx[rt].fi = a[l]; mx[rt].se = l; return; } int mid = l + r >> 1; build(a, lson); build(a, rson); mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]); } void update(int p, int l, int r, int rt) { if(l == r) { mx[rt].fi = 0; return; } int mid = l + r >> 1; if(p <= mid) update(p, lson); else update(p, rson); mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]); } PII query(int L, int R, int l, int r, int rt) { if(R < l || r < L || R < L) return mk(0, 0); if(L <= l && r <= R) return mx[rt]; int mid = l + r >> 1; return max(query(L, R, lson), query(L, R, rson)); }} Tree;int main() { int T; scanf("%d", &T); while(T--) { segEnd.clear(); scanf("%d", &n); segEnd.insert(n + 1); segEnd.insert(0); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); pos[a[i]] = i; ban[i] = false; from[i] = i; } Tree.build(a, 1, n, 1); for(int i = 1; i <= n; i++) { int p = pos[i]; if(ban[p]) continue; int R = from[p]; PII tmp1 = mk(0, 0), tmp2 = mk(0, 0); auto it = segEnd.lower_bound(p); if(*it != p + 1) tmp1 = mk(a[p + 1], p + 1); --it; int L = *it + 1; tmp2 = Tree.query(L, R, 1, n, 1); if(tmp1 > tmp2) { ans[i] = tmp1.fi; from[tmp1.se] = from[p]; Tree.update(tmp1.se, 1, n, 1); } else { ans[i] = tmp2.fi; L = tmp2.se, R = p; for(int j = L; j <= R; j++) { Tree.update(j, 1, n, 1); ban[j] = true; if(j < R) ans[a[j]] = a[j + 1]; } segEnd.insert(p); segEnd.insert(L); } } for(int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]); } return 0;}/**/