#P13100. [FJCPC 2025] 众数

[FJCPC 2025] 众数

题目描述

nn 个整数构成的序列 aia_i(下标 1n1\sim n),对于序列的每个前缀 a1,a2,,aka_1,a_2,\cdots,a_k1kn1\leq k\leq n),考虑选择其中一个非空下标集合 SS,定义 f(S)=min{aiiS}+max{aiiS}f(S)=\min\{a_i\mid i\in S\}+\max\{a_i\mid i\in S\}

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

输入格式

第一行一个整数 tt1t10001\leq t\leq 1000),表示接下来有 tt 组测试数据。

接下来对于每一组测试数据,第一行包含一个整数 nn1n1061\leq n\leq 10^6),表示整数的个数。

接下来一行包含 nn 个整数表示 aia_i1ai1091\leq a_i\leq 10^9)。

保证所有测试数据的 nn 的总和不超过 10610^6

输出格式

对于每一组数据输出一行,包含 nn 个由空格隔开的整数,依次表示每一个前缀的 f(S)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

提示

11 个数中,22 出现了 11 次,最大众数为 22

22 个数中,22 出现了 33 次,最大众数为 22

33 个数中,22 出现了 33 次,55 出现了 33 次,88 出现了 11 次,最大众数为 55

44 个数中,22 出现了 33 次,55 出现了 33 次,66 出现了 66 次,88 出现了 11 次,99 出现了 11 次,1010 出现了 11 次,最大众数为 66

55 个数中,22 出现了 77 次,55 出现了 77 次,66 出现了 1414 次,88 出现了 11 次,99 出现了 11 次,1010 出现了 11 次,最大众数为 66

66 个数中,22 出现了 77 次,55 出现了 2121 次,66 出现了 2828 次,88 出现了 33 次,99 出现了 33 次,1010 出现了 11 次,最大众数为 66