#L3707. 「ZJOI2022」众数

    ID: 4456 传统题 3000ms 1024MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>数据结构单调队列线段树树状数组Hashing其他双指针扫描离散化思维构造贪心难度省选/NOI-

「ZJOI2022」众数

题目描述
九条可怜是一个有超能力的女孩子,但她的超能力只能作用于一些奇怪的事情上。

有一天,可怜得到了一个序列 a1,a2,,ana_1, a_2, \ldots, a_n,她可以对这个序列使用一次超能力: 选择一个区间 [l,r][l, r]1lrn1 \le l \le r \le n)和一个整数 k[109,109]k \in [-10^9, 10^9],将区间内的所有数 al,al+1,,ara_l, a_{l + 1}, \ldots, a_r 加上 kk

九条可怜很喜欢长得比较一致的序列,因此她希望最终的序列众数的出现次数尽可能多。给出序列 aa,你需要输出最终序列的众数出现次数的最大值,并输出这个众数的所有可能取值。注意对于一个序列,众数的取值可能不止一个。


输入格式
输入包含多组数据,第一行输入数据组数 TT

对于接下来的每组数据,第一行输入序列长度 nn,第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n


输出格式
对于每组数据,第一行输出最终序列众数的出现次数的最大值。

假设这个众数有 kk 种不同的可能取值,则接下来 kk 行,从小到大输出这些取值。


样例 1
输入:

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

输出:

4
1
5
1
4
2
4
8
2
1
2
3
4
5

样例 2
见附加文件下的mode_ex2.inmode_ex2.ans


数据范围与提示
对于所有测试点:1T201 \le T \le 202n2×1052 \le n \le 2 \times 10^51ai1091 \le a_i \le 10^9,保证 n5×105\sum n \le 5 \times 10^5,且 aia_i 不全相等。

每个测试点的具体限制见下表:

测试点编号 n\sum n \le nn \le 特殊限制
1~4 3000 300
5~8 5×1055 \times 10^5 2×1052 \times 10^5 aia_i 只有 5 种取值
9~10 2×1052 \times 10^5 50000
11~20 5×1055 \times 10^5 2×1052 \times 10^5