题目描述

有 $n$ 个整数构成的序列 $a_i$（下标 $1\sim n$），对于序列的每个前缀 $a_1,a_2,\cdots,a_k$（$1\leq k\leq n$），考虑选择其中一个非空下标集合 $S$，定义 $f(S)=\min\{a_i\mid i\in S\}+\max\{a_i\mid i\in S\}$。

求对于序列 $a$ 的每个前缀，在其对应的 $2^k-1$ 种情况下，$f(S)$ 的值的众数（出现最多的数），如果有多种数出现次数一样均为最多，则输出其中最大的数。

输入格式

第一行一个整数 $t$（$1\leq t\leq 1000$），表示接下来有 $t$ 组测试数据。

接下来对于每一组测试数据，第一行包含一个整数 $n$（$1\leq n\leq 10^6$），表示整数的个数。

接下来一行包含 $n$ 个整数表示 $a_i$（$1\leq a_i\leq 10^9$）。

保证所有测试数据的 $n$ 的总和不超过 $10^6$。

输出格式

对于每一组数据输出一行，包含 $n$ 个由空格隔开的整数，依次表示每一个前缀的 $f(S)$ 的值的最大众数。

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

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

提示

前 $1$ 个数中，$2$ 出现了 $1$ 次，最大众数为 $2$；

前 $2$ 个数中，$2$ 出现了 $3$ 次，最大众数为 $2$；

前 $3$ 个数中，$2$ 出现了 $3$ 次，$5$ 出现了 $3$ 次，$8$ 出现了 $1$ 次，最大众数为 $5$；

前 $4$ 个数中，$2$ 出现了 $3$ 次，$5$ 出现了 $3$ 次，$6$ 出现了 $6$ 次，$8$ 出现了 $1$ 次，$9$ 出现了 $1$ 次，$10$ 出现了 $1$ 次，最大众数为 $6$；

前 $5$ 个数中，$2$ 出现了 $7$ 次，$5$ 出现了 $7$ 次，$6$ 出现了 $14$ 次，$8$ 出现了 $1$ 次，$9$ 出现了 $1$ 次，$10$ 出现了 $1$ 次，最大众数为 $6$；

前 $6$ 个数中，$2$ 出现了 $7$ 次，$5$ 出现了 $21$ 次，$6$ 出现了 $28$ 次，$8$ 出现了 $3$ 次，$9$ 出现了 $3$ 次，$10$ 出现了 $1$ 次，最大众数为 $6$。