#P18142. Increasing Income

Increasing Income

Increasing Income

对一个序列a,定义f(a)为它的前缀最大值数量,即满足a_i=max(a_1,...,a_i)的位置i的个数。

给定一个1到n的排列p。请构造一个1到n的排列q,使

$$f((q_1,q_2,\ldots,q_n))+f((p_{q_1},p_{q_2},\ldots,p_{q_n}))$$

最大。若有多个最优答案,输出任意一个。

输入格式

第一行一个整数t,1≤t≤100000,表示测试组数。

每组测试先输入一个整数n,1≤n≤200000;下一行n个整数p_1,...,p_n,是1到n的一个排列。

保证所有测试的n之和不超过200000。

输出格式

对每组测试输出n个整数q_1,...,q_n,是1到n的一个排列,并使题述目标最大。

样例

3
3
1 2 3
4
2 4 3 1
5
1 5 2 4 3
1 2 3
1 3 4 2
1 3 5 4 2

说明

第一组,两序列均为(1,2,3),得分3+3=6。第二组得到(1,3,4,2)与(2,3,1,4),得分3+3=6。第三组得到(1,3,5,4,2)与(1,2,3,4,5),得分3+5=8。