Annihilator Gun

In the Link-Cut system, there are $n$ planets, each with its own type. The type of a planet is an integer ranging from $1$ to $k$. 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 planets to any other types (from $1$ to $k$) 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 $1$ to $k$ such that $x_i\ne a_i$ for all $i$, 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.

Input

The first line contains two integers $n$ and $k$ $(1\le n,k\le 10^5)$ — the number of planets and the number of possible types for each planet.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(1\le a_i\le k)$ — the types of the planets.

Output

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 $-1$ if it is impossible.

Examples

Note

In the first example, you can do the only use of the gun, changing the types of both planets to $3$. Since their initial types are different, the answer cannot be $0$.

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. $[1,2,3,1]-[2,3,2,3]$

2. $[2,3,2,3]-[1,1,1,1]$

It can be shown that the condition cannot be satisfied in one use of the gun.

Scoring

1. ($2$ points): $n=1$;

2. ($4$ points): $k=1$;

3. ($8$ points): $n=2$;

4. ($8$ points): $k=2$;

5. ($10$ points): $n\le 100,k\le 100$;

6. ($18$ points): no additional constraints.