Description

Given a sequence $a$ of length $n$, we construct a sequence $b$ in the following way:

• Initially, $b=a$.
• Then perform $k$ operations on $b$ in order. In each operation, choose any one element and modify it to any integer.

dXqwq defines the mode of a sequence as all numbers with the highest frequency. For example, the mode of $[1,1,4,5,1,4]$ is $1$, while the mode of $[1,14,5,14,19,19,8,10]$ is $14,19$.

You need to find how many integers can possibly become the mode of $b$.

Input Format

The first line contains two integers $n,k$.

The second line contains $n$ integers $a_i$.

Output Format

Output one integer, representing the number of values that can possibly become the mode.

In particular, if the answer is positive infinity, output pigstd.

5 0
1 2 3 4 5

5

5 1
1 2 3 4 5

pigstd

5 1
1 1 2 2 3

3

Hint

[Sample Explanation]

For the first group of testdata, in the end $1,2,3,4,5$ can be the mode of the interval.

For the second group of testdata, after changing the first number to $6,7,8,9,\cdots$, all of them will become the mode of the interval, so the answer is positive infinity.

For the third group of testdata, $1,2,3$ can become the mode of the interval.

[Hint]

Allocating $10^6$ std::deque may not necessarily cause MLE when the memory limit is 1024MB.

[Constraints]

This problem uses bundled testcases.

• Subtask 1 (20 pts): $n\leq 5$.
• Subtask 2 (20 pts): $n\leq 10^3$.
• Subtask 3 (20 pts): $k=0$.
• Subtask 4 (20 pts): $k=1$.
• Subtask 5 (20 pts): no special constraints.

For all data, $1\leq n\leq 10^6$, $0\leq k\leq n$, $1\leq a_i\leq n$.

Translated by ChatGPT 5