#P18703. Are you a bot?

Are you a bot?

Are you a bot?

“如果把机器人的心跳排列成一张图,它会是什么样子?”

你有一个算法竞赛机器人,它的心脏每分钟跳动 nn 次。第 ii 次心跳的强度为 aia_i,其中 a1,…,ana_1,\ldots,a_n 是 1,…,n1,\ldots,n 的一个排列。

设 AiA_i 为从序列 aa 中删除第 ii 个元素得到的序列,即

Ai=[a1,…,ai−1,ai+1,…,an].A_i=[a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_n].

对于元素两两不同的序列 pp,定义无向图 G(p)G(p):图中有 ∣p∣|p| 个顶点,编号为 1,…,∣p∣1,\ldots,|p|。对每一对整数 1≤i<j≤∣p∣1\le i<j\le |p|,当且仅当对所有整数 k∈[i,j]k\in[i,j] 都有

min⁡(pi,pj)≤pk≤max⁡(pi,pj),\min(p_i,p_j)\le p_k\le\max(p_i,p_j),

在顶点 i,ji,j 之间连一条边。

定义 F(p)F(p) 为 G(p)G(p) 中从顶点 11 到顶点 ∣p∣|p| 的最短路径长度,路径长度按边数计算。再定义

f(a)=[F(A1),F(A2),…,F(An)].f(a)=[F(A_1),F(A_2),\ldots,F(A_n)].

给定长度为 nn 的序列 b1,…,bnb_1,\ldots,b_n,请构造任意一个 1,…,n1,\ldots,n 的排列 aa,使得 f(a)=bf(a)=b。保证至少存在一个解。

输入格式

第一行包含一个整数 TT(1≤T≤400001\le T\le40000),表示测试用例数。

每个测试用例的第一行包含一个整数 nn(4≤n≤1054\le n\le10^5);第二行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n。

保证每个测试用例都有解。保证一个输入文件中所有测试用例的 nn 之和不超过 5×1055\times10^5。

输出格式

对每个测试用例输出一行 nn 个整数 a1,…,ana_1,\ldots,a_n,表示你构造的排列。如果有多个解,输出任意一个。

样例输入

11
4
2 2 1 1
4
2 2 2 2
4
2 1 1 2
7
5 5 4 4 4 5 5
7
1 3 2 2 2 2 4
7
3 3 2 4 4 5 3
8
2 2 3 5 3 3 3 4
8
5 4 4 4 4 6 6 5
8
4 4 4 2 4 4 2 3
9
4 7 5 5 5 5 3 4 4
9
3 4 4 4 4 4 4 4 6

样例输出

1 2 4 3
2 1 4 3
1 3 2 4
3 1 7 2 6 4 5
3 1 6 4 2 5 7
2 3 1 6 4 7 5
5 6 3 1 7 4 2 8
1 8 2 7 3 5 6 4
6 3 2 7 4 5 1 8
5 8 6 3 7 1 9 2 4
8 1 7 9 2 5 3 4 6

样例输出只是各测试用例的一组可行解。