问题描述
Peter有一个序列$a_1,a_2,...,a_n$. 定义$F(a_1,a_2,...,a_n)=(f_1,f_2,...,f_n)$, 其中$f_i$是以$a_i$结尾的最长上升子序列的长度.
Peter想要找到另一个序列$b_1,b_2,...,b_n$使得$F(a_1,a_2,...,a_n)$和$F(b_1,b_2,...,b_n)$相同. 对于所有可行的正整数序列, Peter想要那个字典序最小的序列.
序列$a_1, a_2, ..., a_n$比$b_1, b_2, ..., b_n$字典序小, 当且仅当存在一个正整数$i$ $(1 \le i \le n)$满足对于所有的$k$ $(1 \le k < i)$都有$a_k = b_k$并且$a_i < b_i$.
输入描述
输入包含多组数据, 第一行包含一个整数$T$表示测试数据组数. 对于每组数据:
第一行包含一个整数$n$ $(1 \le n \le 100000)$表示序列的长度. 第二行包含$n$个整数$a_1,a_2,...,a_n$ $(1 \le a_i \le 10^9)$.
输出描述
对于每组数据, 输出$n$个整数$b_1,b_2,...,b_n$ $(1 \le b_i \le 10^9)$表示那个字典序最小的序列.
输入样例
3
1
10
5
5 4 3 2 1
3
1 3 5
输出样例
1
1 1 1 1 1
1 2 3
