Annihilator Gun#11727
In the Link-Cut system, there are planets, each with its own type. The type of a planet is an integer ranging from to . You are given an array of integers a_1, a_2, \dots, a_n representing the types of each planet. Your goal is to make all planets of the same type or determine that it is impossible.
To achieve this, Lucy has constructed an annihilator gun for you, which can change the types of each planet to any other types (from to ) that are not equal to their previous types in one use. The new types of planets do not necessarily have to be distinct.
More formally, in one use of the gun, you can create an array x_1, x_2, \dots, x_n of integers from to such that x_i \neq a_i for all , and then assign each element of the array a_i a new value x_i.
Since using the annihilator gun is quite resource-intensive, and you need to save resources for capturing the evil Chmyaaax, you need to achieve the goal in the minimum number of uses of the gun. Your task is to determine this number or to determine that it is impossible to make all planets of one type.
The first line contains two integers and (1 \le n, k \le 10^5) — the number of planets and the number of possible types for each planet.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le k) — the types of the planets.
In a single line, you need to output the minimum number of uses of the annihilator gun required to make all planets of the same type or if it is impossible.
Example
Example 1
Example 2
Example 3
In the first example, you can do the only use of the gun, changing the types of both planets to . Since their initial types are different, the answer cannot be .
In the second example, it can be shown that it is not possible to make both planets of the same type.
In the third example, all the planets have the same type initially, thus you do not need to do anything.
In the fourth example, you can use the gun two times:
[1, 2, 3, 1] - [2, 3, 2, 3]
[2, 3, 2, 3] - [1, 1, 1, 1]
It can be shown that the condition cannot be satisfied in one use of the gun.
( points): n = 1;
( points): k = 1;
( points): n = 2;
( points): k = 2;
( points): n \le 100,\,k \le 100;
( points): no additional constraints.