U. 「EZEC-14」众数 I

Type: RemoteJudge

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

pigstd 是一个可爱的男孩子。他在 NOI2022 中的众数一题定义了 $10^6$ 个 std::deque 并没有 MLE。

给定一个长度为 $n$ 的序列 $a$ ，我们通过以下方式构造序列 $b$ ：

dXqwq 定义一个序列的众数为所有出现次数最大的数。例如 $[1,1,4,5,1,4]$ 的众数为 $1$ ，而 $[1,14,5,14,19,19,8,10]$ 的众数为 $14,19$ 。

你需要求出有多少整数可能成为 $b$ 的众数。

第一行输入两个整数 $n,k$ 。

第二行输入 $n$ 个整数 $a_i$ 。

输出一个整数，代表可能成为众数的数的数量。

特别地，如果答案为正无穷，输出 pigstd。

5 0
1 2 3 4 5

5 1
1 2 3 4 5

pigstd

5 1
1 1 2 2 3

【样例解释】

对于第一组数据，最终 $1,2,3,4,5$ 可能为区间众数。

对于第二组数据，将第一个数换成 $6,7,8,9,\cdots$ 后它们均会成为区间众数，因此答案为正无穷。

对于第三组数据， $1,2,3$ 可能成为区间众数。

【提示】

开 $10^6$ 个 std::deque 在空间限制为 1024MB 时不一定会 MLE。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据， $1\leq n\leq 10^6$ ， $0\leq k\leq n$ ， $1\leq a_i\leq n$ 。