记录编号	605977	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	4175.[USACO25 Feb Silver]The Best Lineup	最终得分	100
用户昵称	Gao	是否通过	通过
代码语言	C++	运行时间	3.544 s
提交时间	2025-09-13 15:45:30	内存使用	4.78 MiB

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005],b[200005],maxx[200005];
int main(){
    freopen("Lineup.in","r",stdin);
    freopen("Lineup.out","w",stdout);
    cin>>t;
    for(int o=1;o<=t;o++){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        maxx[n+1]=0;
        for(int i=n;i>=1;i--){
            maxx[i]=max(a[i],maxx[i+1]);
        }
        
        int zhi=0,k=0;
        for(int i=1;i<=n;i++){
            if(maxx[i]==a[i]){
                if(zhi>=maxx[i+1]){
                    for(int j=i;j>k+1;j--){
                        swap(a[j],a[j-1]);
                    }
                    break;
                }
                k=i;
                zhi=0;
            }
            else{
                zhi=max(a[i],zhi);
            }
        }
        int cnt=0,ji=0;
        for(int i=1;i<=n;i++){
            if(i!=1&&a[i]>b[cnt]){
                
                while(a[i]>b[cnt]){
                    cnt--;
                    if(cnt==0){
                        break;
                    }
                }
//                cout<<i<<" ";
            }
//            cout<<endl;
            cnt++;
            b[cnt]=a[i];
        }
//        for(int i=1;i<=n;i++){
//            cout<<a[i]<<" ";
//        }
//        cout<<endl;
        for(int i=1;i<=cnt;i++){
            cout<<b[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}