You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 生活的 Z 市位于一个狭长的盆地，因此形成了独有的奇观——所有的楼房是排成一列建造的！

具体的，Z 市一共有 $n$ 个建筑从东到西依次排列，第 $i$ 个建筑的高度为 $a_i$ 米。Z 市的设计师们为了体现不同建筑的区别，保证了这些高度 $a_1,a_2,\cdots,a_n$ 构成了一个 $1,2,\dots,n$ 的排列。

Z 市的人们相信一栋建筑是“楼王”，当且仅当所有它东侧的建筑都比它矮。换言之，第 $i$ 个建筑是“楼王”当且仅当 $a_i>\max(a_1,a_2,\dots,a_{i-1})$ 。Z 市的人们都很喜欢楼王，所以定义 Z 市的美观度为“楼王”的个数。

现在 Z 市的市长小 Z 决定将这些楼房重建，但推倒的代价太大，于是小 Z 选择了小 Y 提供的新技术 “乾坤大挪移”。具体的，一次乾坤大挪移基于一个预先设置的 $1,2,\cdots,n$ 的排列 $b_1,b_2,\dots,b_n$，执行完乾坤大挪移后，原本在从东到西的第 $b_i$ 个建筑会被移到从东到西的第 $i$ 个位置。

执行乾坤大挪移同样有一定的代价。小 Y 注意到，对于排列 $b$ 中的每一个数 $b_i$ ，如果存在某个$j<i$ 满足 $b_j>b_i$，那么在 $b_i$ 处就会产生 $1$ 的代价（每个位置 $i$ 最多只会产生 $1$ 的代价）。现在小 Y 请你来给他出谋划策，请你为他寻找一个 $1,2,\cdots,n$ 的排列 $b_1,b_2,\dots,b_n$，使得按此执行完“乾坤大挪移”后，Z 市的美观度减去乾坤大挪移的代价最大。

输入格式

从 rebuild.in 文件读入数据。

第一行一个整数 $T$，代表数据组数。对于每组数据：

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，代表 Z 市的建筑初始的高度，保证 $a_1,a_2,\cdots,a_n$ 是 $1,2,\dots,n$ 的一个排列。

输出格式

输出到 rebuild.out 文件。

对于每组测试数据，输出一行 $n$ 个整数 $b_1,b_2,\cdots,b_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$，乾坤大挪移的代价为 $0$。

对于样例中的第二个数据，乾坤大挪移后从东到西的高度为 $2,3,1,4$，楼王的个数为 $3$，乾坤大挪移的代价为 $1$。

对于样例中的第三个数据，乾坤大挪移后从东到西的高度为 $1,2,3,4,5$，楼王的个数为 $5$，乾坤大挪移的代价为 $2$。

数据范围

对于每个测试点，$1 \leq T\leq 10^5$，$1 \leq n\leq 2\times 10^5$，$T$ 组数据的 $n$ 之和不超过 $2\times 10^5$。