Увлекшись машинным обучением, Вася совсем забыл про свои экзамены в университете, завалил их и пошел служить в армию. Однако, и тут ему пригодились его навыки программиста — у работников столовой возникла проблема с тем, что блюда постоянно повторяются, и солдаты начали слишком этому возмущаться. Узнав, что Вася разбирается в программировании, работники попросили его написать программу, которая сделает распределение блюд.
Работники столовой считают, что единственное, что характеризует распределение блюд — их «степень монотонности» — число одинаковых блюд, которые даются в последовательные приемы пищи. То есть, если представить расписание блюд как массив a, то «степень монотонности» будет равна количеству индексов i, таких что a
i = a
i - 1. Для начала вас просят найти не само распределение блюд, а хотя бы минимальную возможную «степень монотонности», которую можно было бы получить некоторой перестановкой заданного набора блюд. Помогите армейской столовой!
Входные данные
В первой строке содержится число n — количество блюд, которые должны войти в расписание (1 ≤ n ≤ 100).
В следующей строке содержится n чисел a
i — блюда (1 ≤ a
i ≤ 100). Одинаковые блюда обозначены одинаковыми числами, разные — разными.
Выходные данные
В единственной строке выведите одно число — минимальное возможное значение «степени монотонности».
| Ввод |
Вывод |
5
1 2 3 1 1 |
0 |
6
1 1 2 3 1 1 |
1 |