题目描述

对于一个长为 $m$ 的序列 $\{b_i\}$，我们称 $x$ 是这个序列的 主元，当且仅当 $x$ 在 $\{b_i\}$ 中出现了至少 $\lfloor\frac m2\rfloor +1$ 次。例如：$[1,1,4]$ 的主元是 $1$，$[1,3,1,3,3,3]$ 的主元是 $3$，$[1,9,1,9]$ 和 $[5,4,3,2,1]$ 没有主元。

给定一个长为 $n$ 的序列 $\{a_i\}$，每次操作可以选择一个 存在主元 的子段 $a[l\ldots r]$，然后将整个 $a[l\ldots r]$ 都赋值为这个主元。

你可以进行 $0$ 次或任意多次操作。求可以获得的字典序最小的序列。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行一个正整数 $n$，代表序列长度；
• 接下来一行 $n$ 个整数，代表序列 $[a_1,a_2,\ldots,a_n]$。

输出格式

对于每组数据，输出一行 $n$ 个整数，代表可以获得的字典序最小的序列。

3
4
2 1 1 2
6
3 4 1 3 2 6
7
4 3 3 4 3 2 5

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

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 20$；
• 对于另外 $30\%$ 的数据，$a_i \le 2$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n,\sum n \le 2 \cdot 10^5$，$1 \le a_i \le n$。