Problem Background

pigstd is a cute boy. He defined $10^6$ std::deques in the Mode problem at NOI2022 without encountering MLE.

Problem Description

Given a sequence \(a\) of length \(n\), we construct sequence \(b\) as follows:

• Initially, \(b = a\).
• Perform \(k\) operations sequentially on \(b\), where each operation selects any element and modifies it to any integer.

dXqwq defines the mode of a sequence as the number(s) that appear most frequently. For example, the mode of \([1,1,4,5,1,4]\) is \(1\), and the mode of \([1,14,5,14,19,19,8,10]\) is \(14,19\).

You need to determine how many integers can potentially become the mode of \(b\).

Input Format

The first line contains two integers \(n\) and \(k\).

The second line contains \(n\) integers \(a_i\).

Output Format

Output a single integer representing the number of possible modes.

Specifically, if the answer is positive infinity, output pigstd.

Sample Input and Output

Sample Input #1

5 0
1 2 3 4 5

Sample Output #1

5

Sample Input #2

5 1
1 2 3 4 5

Sample Output #2

pigstd

Sample Input #3

5 1
1 1 2 2 3

Sample Output #3

3

Notes

[Sample Explanation]

For the first set of data, \(1,2,3,4,5\) can potentially be the mode.

For the second set of data, replacing the first number with \(6,7,8,9,\cdots\) will make them all potential modes, hence the answer is positive infinity.

For the third set of data, \(1,2,3\) can potentially be the mode.

[Hint]

Creating \(10^6\) std::deques within a 1024MB memory limit may not necessarily result in MLE.

[Data Range]

This problem uses subtask testing.

• 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 restrictions.

For \(100\%\) of the data, \(1 \leq n \leq 10^6\), \(0 \leq k \leq n\), \(1 \leq a_i \leq n\).

见题面 Input 部分

见题面 Output 部分