← 返回题目列表

Codeforces · 626/E

E. 简单偏度

中文机器翻译题面 查看原题

将数字集合的简单偏度定义为集合的平均值减去中位数。给你一个包含 n 个(不一定不同)整数的列表。找到具有最大简单偏度的非空子集(有重复)。

集合的平均值是其元素的平均值。当集合的所有元素都已排序时,集合的中位数是其中间元素;如果集合的大小为偶数,则中位数是其两个中间元素的平均值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 列表中的元素数量。

第二行包含 n 个整数 xi (0 ≤ xi ≤ 1 000 000) — 列表的第 i 个元素。

输出

在第一行中,打印一个整数 k — 子集的大小。

在第二行中,打印 k 个整数 — 子集的元素以任意顺序排列。

如果有多个最佳子集,则打印任何一个。

示例

输入 #1

4
1 2 3 12

输出 #1

3
1 2 12

输入 #2

4
1 1 2 2

输出 #2

3
1 1 2

输入 #3

2
1 2

输出 #3

2
1 2

注意

在第一种情况下,最佳子集是 $${ \{ 1, 2, 1 2 \} }$$,其平均值为 5,中位数为 2,简单偏度为 5 - 2 = 3。

在第二种情况下,最优子集是 $${ \{ 1, 1, 2 \} }$$。请注意,允许重复。

在最后一种情况下,任何子集都具有相同的中值和均值,因此所有子集的简单偏度均为 0。