АНИГИЛЯТОРНАЯ ПУШКА
В системе Link-Cut есть планет, каждая из которых имеет свой тип. Тип планеты — это целое число, от до . Вам дан массив целых чисел , представляющий собой типы каждой планеты. Ваша цель — сделать так, чтобы все планеты были одного типа, или определить, что это невозможно.
Для достижения этой цели Люси сконструировала для вас анигиляторную пушку, которая может, за один выстрел , изменить типы каждой планеты на любые другие (от до ), которые не равны их предыдущим типам. Новые типы планет не обязательно должны быть различными.
Более формально, за один выстрел оружия вы можете задать массив целых чисел от до так, что для всех , а затем присвоить каждому элементу массива новое значение .
Поскольку использование этой пушки довольно ресурсозатратное, а вам нужно сэкономить ресурсы для поимки злого Чмяяякса , то есть достичь цели за минимальное количество выстрелов. Ваша задача — определить это число или выяснить, что сделать все планеты одного типа невозможно.
Входные данные
Первая строка содержит два целых числа и — количество планет и количество возможных типов для каждой планеты.
Вторая строка содержит целых чисел — типы планет.
Выходные данные
В одной строке вам нужно вывести минимальное количество выстрелов пушки, необходимых для того, чтобы сделать все планеты одного типа, или , если это невозможно.
Примеры
Примечание
В первом примере вы можете сделать единственный выстрел, изменив типы обеих планет на . Поскольку их начальные типы различны, ответ не может быть .
Во втором примере можно показать, что невозможно сделать так, чтобы обе планеты были одного типа.
В третьем примере все планеты изначально имеют один и тот же тип, поэтому вам не нужно ничего делать.
В четвертом примере вы можете использовать оружие дважды:
Можно показать, что условие не может быть выполнено за одно использование оружия.
Оценивание
( балла): ;
( балла): ;
( баллов): ;
( баллов): ;
( баллов): ;
( баллов): без дополнительных ограничений.