题意
重组给定的正整数序列，使 最大。
思路
根据贪心策略易得，构造使上式最大的数列的策略是将最大的元素放在中间位置，然后从大到小在中间元素的左右各放一个元素。按该做法直接构造数列可以得到数列中无重复元素的部分分。
在有重复元素的数列中，首先必须满足中间元素两边各分布一个重复元素。在满足该条件的情况下，如果该元素的字典序比恰好比它大一点的元素（即排序后 和 的关系）要小，则排在已分布元素的左侧，反之则放在右侧。
在实践中，我们可以灵活选择枚举方式。本篇题解中，我使用了从两侧向中间枚举的方法，优点是可以在不使用双端队列的情况下节约空间。
code
#include<bits/stdc++.h>
#define ll int
#define R register
#define mod 1234567891
using namespace std;
inline ll read(){ll f=0,pa=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')pa=-1;ch=getchar();}while(ch>='0'&&ch<='9'){f=(f<<3)+(f<<1)+(ch^48);ch=getchar();}return f*pa;
}
inline void write(ll x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writelp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
ll t,n,a[400005],s,e,pan,pa,ji,ans[400005],las,d[100005];
struct node{ll w,id;
}p[100005];
bool cmp(node a,node b){if(a.w!=b.w)return a.w<b.w;else return a.id<b.id;
}
int main(){/*freopen("permutation.in","r",stdin);freopen("permutation.out","w",stdout);*/t=read();while(t--){n=read();s=0;e=n+1;pa=0;ji=0;for(R ll i=1;i<=n;i++)p[i].w=read(),p[i].id=i,d[i]=p[i].w;sort(p+1,p+n+1,cmp);for(R ll i=1;i<=n-1;i++){pan=(pan^1);if(p[i].w!=p[i+1].w){if(ji==0){ji=1;if(p[i].id<p[i+1].id)pan=1,a[++s]=p[i].id;else pan=0,a[--e]=p[i].id;}else if(pan==0) a[--e]=p[i].id;else a[++s]=p[i].id;}else{ll j,ee=e,ss=s;for(j=i+1;j<=n;j++)if(p[j].w!=p[i].w)break;j--;ll mini;if(j<=n-2)mini=min(p[j+1].id,p[j+2].id);if(j==n-1)mini=p[j+1].id;if(j==n)j--,mini=p[n].id,ss=0,ee=0;for(R ll k=i;k<=j;k++)if(p[k].id<mini) a[++s]=p[k].id;for(R ll k=j;k>=i;k--)if(p[k].id>mini) a[--e]=p[k].id;if(s==ss) a[++s]=a[e++];if(e==ee) a[--e]=a[s--];i=j;ji=0;}}a[(s+e)/2]=p[n].id;for(R ll i=1;i<=n;i++)writelp(a[i]);cout<<endl;}return 0;
}