Possible Mode Candidates

You are given a sequence \(a\) of length \(n\). We construct a new sequence \(b\) from \(a\) by performing exactly \(k\) operations. In each operation, you may choose any element of \(b\) and change its value to any integer. Initially, \(b=a\).

The mode of a sequence is defined as the number (or numbers) that occur most frequently. For example, the mode of \([1,1,4,5,1,4]\) is \(1\), while the modes of \([1,14,5,14,19,19,8,10]\) are \(14\) and \(19\).

Your task is to determine how many integers can possibly be a mode of \(b\) after the operations are performed. If there are infinitely many possibilities, output -1.

Important note on operations: In each operation, you can pick any index (even the same index more than once, though doing so repeatedly is unnecessary) and assign it an arbitrary integer. Thus, you have control over exactly \(k\) positions of the final sequence.

Hint: You do not necessarily need to use the operations to increase the frequency of an integer from the original sequence, you can also use them to reduce the frequencies of competitors. When \(k\) is large (in fact, when \(k\ge n\)), you can modify all entries in \(a\) so that \(b\) is constant – hence, every integer is possible (i.e. infinitely many answers).

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le k \le 10^9,\; 1 \le n \le 10^5)\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((|a_i| \le 10^9)\) representing the sequence \(a\).

outputFormat

Output a single integer. If there are infinitely many integers that can become the mode of \(b\), print -1. Otherwise, print the number of integers that can possibly be the mode of \(b\) after exactly \(k\) modifications.

sample

6 1
1 1 4 5 1 4

3