Анігіляторна гармата#11727
В системі Link-Cut є планет, кожна з яких має свій тип. Тип планети — це ціле число від до . Вам дано масив цілих чисел a_1, a_2, \dots, a_n, що представляє типи кожної планети. Ваша мета — зробити так, щоб усі планети були одного типу, або визначити, що це неможливо.
Для досягнення цієї мети Люсі сконструювала для вас анігіляторну гармату, яка може, за один постріл, змінити типи кожної планети на будь-які інші (від до ), які не дорівнюють їх попереднім типам. Нові типи планет не обов'язково повинні бути різними.
Більш формально, за один постріл зброї ви можете задати масив x_1, x_2, \dots, x_n цілих чисел від до так, що x_i \neq a_i для всіх , а потім присвоїти кожному елементу масиву a_i нове значення x_i.
Оскільки використання цієї гармати досить ресурсозатратне, а вам потрібно заощадити ресурси для спіймання злого Чмяяякса, потрібно досягти мети за мінімальну кількість пострілів. Ваша задача — визначити це число або з'ясувати, що зробити всі планети одного типу неможливо.
Перша строка містить два цілих числа і (1 \le n,\, k \le 10^5) — кількість планет і кількість можливих типів для кожної планети.
Друга строка містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le k) — типи планет.
В одній строкі вам потрібно вивести мінімальну кількість пострілів гармати, необхідних для того, щоб зробити всі планети одного типу, або , якщо це неможливо.
Приклад
Приклад 1
Приклад 2
Приклад 3
У першому прикладі ви можете зробити єдиний постріл, змінивши типи обох планет на . Оскільки їх початкові типи різні, відповідь не може бути .
У другому прикладі можна показати, що неможливо зробити так, щоб обидві планети були одного типу.
У третьому прикладі всі планети спочатку мають один і той же тип, тому вам не потрібно нічого робити.
У четвертому прикладі ви можете використати гармату двічі:
[1,\, 2,\, 3,\, 1] - [2,\, 3,\, 2,\, 3]
[2,\, 3,\, 2,\, 3] - [1,\, 1,\, 1,\, 1]
Можна показати, що умова не може бути виконана за одне використання гармати.
( бали): n = 1;
( бали): k = 1;
( балів): n = 2;
( балів): k = 2;
( балів): n \le 100,\, k \le 100;
( балів): без додаткових обмежень.