АНіГіЛЯТОРНА ПУШКА

В системі Link-Cut є $n$ планет, кожна з яких має свій тип. Тип планети — це ціле число, від $1$ до $k$. Вам дано масив цілих чисел $a_1,a_2,\dots ,a_n$, що представляє типи кожної планети. Ваша мета — зробити так, щоб усі планети були одного типу, або визначити, що це неможливо.

Для досягнення цієї мети Люсі сконструювала для вас анігіляторну пушка, яка може, за один постріл, змінити типи кожної планети на будь-які інші (від $1$ до $k$), які не рівні їх попереднім типам. Нові типи планет не обов'язково повинні бути різними.

Більш формально, за один постріл зброї ви можете задати масив $x_1,x_2,\dots ,x_n$ цілих чисел від $1$ до $k$ так, що $x_i\ne a_i$ для всіх $i$, а потім присвоїти кожному елементу масиву $a_i$ нове значення $x_i$.

Оскільки використання цієї пушки досить ресурсозатратне, а вам потрібно заощадити ресурси для спіймання злого Чмяяякса, тобто досягти мети за мінімальну кількість пострілів. Ваша задача — визначити це число або з'ясувати, що зробити всі планети одного типу неможливо.

Вхідні дані

Перша строка містить два цілих числа $n$ і $k$ $(1\le n,k\le 10^5)$ — кількість планет і кількість можливих типів для кожної планети.

Друга строка містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(1\le a_i\le k)$ — типи планет.

Вихідні дані

В одній строкі вам потрібно вивести мінімальну кількість пострілів гармати, необхідних для того, щоб зробити всі планети одного типу, або $-1$, якщо це неможливо.

Приклади

Примітка

В першому прикладі ви можете зробити єдиний постріл, змінивши типи обох планет на $3$. Оскільки їх початкові типи різні, відповідь не може бути $0$.

У другому прикладі можна показати, що неможливо зробити так, щоб обидві планети були одного типу.

У третьому прикладі всі планети спочатку мають один і той же тип, тому вам не потрібно нічого робити.

У четвертому прикладі ви можете використовувати зброю двічі:

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

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

Можна показати, що умова не може бути виконана за одне використання зброї.

Оцінювання

1. ($2$ бали): $n=1$;

2. ($4$ бали): $k=1$;

3. ($8$ балів): $n=2$;

4. ($8$ балів): $k=2$;

5. ($10$ балів): $n\le 100,k\le 100$;

6. ($18$ балів): без додаткових обмежень.