怎么还会新建一种元素的。不过没有这种情况也称不上 *3400 了。

首先有一个显然的观察： 对于一个数 ，只有其出现的最左/最右位置会对子区间权重产生影响。那么，可以将每个序列中的数抽象为一个三元组 。

容易发现，对于 ，且 的 包含了 的 ，那 就不可能是任何子区间的权重，这个数就没用了。

删去这样的数之后，所有的数都会是某个子区间的权重，而且，这样的数的两个端点都已经确定，不会改变。

考虑如何填写那些并不是某个数的区间端点的位置。

一个显然的想法是对位置 ，填 包含它的 中 最大者，下文设这个值为 。但你发现这么写过不了样例中 1 1 1 1 4 4 3 3 3 的数据。然后你惊奇地发现答案中出现了原序列没有的数。

不过好消息是，只会出现一种新的数，因为如果出现了两种，显然可以把小的数全都变成大的数，子区间权重不变。

设这个数为 。假设我们已经知道了 的左右端点 ，那就必须存在一个 的 ，使得 ，否则 就会成为某个子区间的权重，产生矛盾。换个角度来说，如果我们枚举这个 ，那么 就必须是小于它的，最大的没有出现过的元素，这样显然是最优的。

考虑枚举 之后怎么填 。我们从大到小枚举 ，并将 的位置先填上 。将 的位置全部填上 。但这么填还不一定能满足上面的条件，所以如果上一步在 的左边没有填上 ，就得找一个 已经填了 的数，将其改为 ，显然找最小的最优。 的右边同理。

于是本题就做完了，时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define FI first
#define SE second
const int N = 1e5 + 5;
int n,a[N];

pii Mn[N << 2];
void pushup(int k) { Mn[k] = min(Mn[k << 1],Mn[k << 1 | 1]);}
void Change(int k,int l,int r,int pos,int v) {
	if(l == r) { Mn[k] = make_pair(v,pos);return;}
	int mid = l + r >> 1;
	if(pos <= mid) Change(k << 1,l,mid,pos,v);
	else Change(k << 1 | 1,mid + 1,r,pos,v);
	pushup(k);
}
pii Query(int k,int l,int r,int x,int y) {
	if(x <= l && r <= y) return Mn[k];
	int mid = l + r >> 1;
	if(y <= mid) return Query(k << 1,l,mid,x,y);
	else if(x > mid) return Query(k << 1 | 1,mid + 1,r,x,y);
	else return min(Query(k << 1,l,mid,x,y),Query(k << 1 | 1,mid + 1,r,x,y));
}
void build(int k,int l,int r) {
	Mn[k] = make_pair(1e9,1e9);
	if(l == r) return;
	int mid = l + r >> 1;
	build(k << 1,l,mid);build(k << 1 | 1,mid + 1,r);
}
vector<int> vals,usd;
map<int,vector<int> > Qu;
int Ans[N];
inline void work() {
	vals.clear();Qu.clear();
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i],Qu[Ans[i] = a[i]].push_back(i);
	for(auto i : Qu) vals.push_back(i.FI);
	build(1,1,n);
	usd.clear();
	reverse(vals.begin(),vals.end());
	for(auto &i : Qu) {
		for(int j = 1;j < i.SE.size() - 1;j++)
			Ans[i.SE[j]] = 0;
	}

	for(auto i : vals) {
		int l = Qu[i][0],r = Qu[i].back();
		if(Query(1,1,n,l,r).FI <= r)
			Ans[l] = Ans[r] = 0;
		else Change(1,1,n,l,r),usd.push_back(i);
	}
	vector<int> lst(usd.size());
	lst.back() = usd.back() - 1;
	for(int j = lst.size() - 2;j >= 0;j--)
		if(usd[j] - 1 != usd[j + 1]) lst[j] = usd[j] - 1;
		else lst[j] = lst[j + 1];

	long long mxans = 0;
	int mxval = 0;
	build(1,1,n);
	set<int> S;
	for(int i = 1;i <= n;i++) if(!Ans[i]) S.insert(i),Change(1,1,n,i,-1);
	long long sum = 0; // 比 t 大的数之和	
	vector<pair<int,int> > Upd;
	int lnew = -1,rnew = -1;
	int poi = 0;
	for(int t = 0;t < usd.size();t++)
	{
		while(poi < usd.size() && usd[poi] > lst[t]) {
			int l = Qu[usd[poi]][0],r = Qu[usd[poi]].back();
			auto it = S.lower_bound(l);
			while(it != S.end() && *it <= r) {
				sum += usd[poi];
				Change(1,1,n,*it,usd[poi]);
				Upd.emplace_back(*it,usd[poi]);
				it = S.erase(it);
			}
			++poi;
		}
		if(!lst[t]) continue;
		int L = Qu[usd[t]][0],R = Qu[usd[t]].back();
		if(L == 1 || R == n) continue;
		pii lp = Query(1,1,n,1,L - 1),rp = Query(1,1,n,R + 1,n);
		if(lp.FI >= 1e9 || rp.FI >= 1e9) continue;
		long long add = lst[t] * S.size() + (lp.FI == -1 ? 0 : lst[t] - lp.FI) + (rp.FI == -1 ? 0 : lst[t] - rp.FI);
		if(lst[t] && sum + add > mxans) {
			mxans = sum + add;
			mxval = lst[t];
			lnew = (lp.FI == -1 ? -1 : lp.SE);
			rnew = (rp.FI == -1 ? -1 : rp.SE);
			while(!Upd.empty()) {
				Ans[Upd.back().FI] = Upd.back().SE;
				Upd.pop_back();
			}
		}
	}
	if(S.size() == 0 && sum > mxans) {
		mxans = sum;
		lnew = rnew = -1;
		while(!Upd.empty()) {
			Ans[Upd.back().FI] = Upd.back().SE;
			Upd.pop_back();
		}
	}
	if(~lnew) Ans[lnew] = 0;
	if(~rnew) Ans[rnew] = 0;
	for(int i = 1;i <= n;i++)
		printf("%d ",Ans[i] ? Ans[i] : mxval);
	printf("\n");
}	
int main()
{
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}