最后悔的一集，感觉 D \(<\) everything。
考虑由确定的点推出其他点的答案，发现最高点的答案是确定的，设其位置为 \(x\)。
然后根据题目定义，发现可以分成 \([1,x-1],[x,n]\) 两个区间，\([x,n]\) 答案均为 \(h_x\)。
对于 \([1,x-1]\) 区间，我们找到第一个 \(>[x,n]\) 区间最小值的位置，设其为 \(y\)，则 \([y,x-1]\) 答案也为 \(h_x\)。
简证：\(y\) 能跳到 \([x,n]\) 区间最小值的位置，然后跳到 \(x\)，对于 \(z>y\)，若其高度 \(>h_y\)，也可以跳到 \([x,n]\) 区间， 若其高度 \(<h_y\)，则可以跳到 \(y\)，进一步跳到 \(x\)。
然后我们再去处理 \([1,y-1]\) 区间即可。
注意若 \([1,x-1]\) 区间最大值也 \(<[x,n]\) 最小值，那么我们找出 \([1,x-1]\) 区间最大值，重复上述过程。
找区间最大值位置，st 表即可。
答案和最小值暴力找即可，找第一个\(>[x,n]\) 区间最小值的位置，预处理前缀最大值，然后二分。
时间复杂度 \(O(nlogn)\)。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define gc getchar()
#define dg(ch) isdigit(ch)
#define _mul(x) ((x<<3)+(x<<1))
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){int x=0,f=1;char ch=gc;while(!dg(ch)){if(ch=='-')f=-1;ch=gc;}while(dg(ch)){x=_mul(x)+(ch^48),ch=gc;}return x*f;}
const int N=5e5+10,INF=1e9;
int T,n,mx[N],f[N][20],a[N],ans[N],mxn,mn;
int cmp(int x,int y){return a[x]>a[y]?x:y;}
int query(int l,int r){
int k=log2(r-l+1);
return cmp(f[l][k],f[r-(1<<(k))+1][k]);
}
void cal(int r){
if(r<1) return;
int res=0,L=1,R=r;
while(L<=R){
int mid=(L+R)>>1;
if(mx[mid]>mn) R=mid-1,res=mid;
else L=mid+1;
}
if(res==0){
int pos=query(1,r);FOR(i,pos,r) ans[i]=a[pos],mn=min(mn,a[i]);
mxn=a[pos],cal(pos-1);return;
}
else{
FOR(i,res,r) ans[i]=mxn,mn=min(mn,a[i]);
cal(res-1);
}
}
void solve(){
FOR(i,1,n) mx[i]=0,a[i]=0,ans[i]=0;mn=INF,mxn=0;
FOR(i,1,n) FOR(j,0,20) f[i][j]=0;
n=rd;FOR(i,1,n) a[i]=rd,mx[i]=max(mx[i-1],a[i]),f[i][0]=i;
int t=log2(n)+1;
FOR(i,1,t-1) for(int j=1;(j+(1<<i))-1<=n;j++) f[j][i]=cmp(f[j][i-1],f[j+(1<<i-1)][i-1]);
int pos=query(1,n);FOR(i,pos,n) ans[i]=a[pos],mn=min(mn,a[i]);
mxn=a[pos],cal(pos-1);
FOR(i,1,n) printf("%d ",ans[i]);cout<<'\n';
}
int main(){
T=rd;
while(T--) solve();
return 0;
}