Дан массив \(a\) из \(n\) целых чисел. У этого массива изначально есть только одна копия, данная вам.
Можно делать два вида действий:
- Выбрать любой массив и создать его копию. После это появляется ещё один массив, равный выбранному.
- Поменять местами два элемента из любых копий (возможно, в одной копии) на любых позициях.
Вам нужно найти минимальное количество действий, необходимое, чтобы хотя бы в одной копии все элементы были равны.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество действий, которое нужно сделать, чтобы хотя бы в одной копии массива все элементы были равны.
Примечание
В первом наборе входных данных в массиве уже все числа равны, поэтому ответ равен \(0\).
Во втором наборе входных данных сначала можно сделать копию данного массива. Тогда будут два одинаковых массива:
\([ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]\) и \([ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]\)
После этого можно поменять местами элементы так, чтобы все нули оказались в одном массиве:
\([ \ 0 \ \underline{0} \ \underline{0} \ 3 \ 7 \ 0 \ ]\) и \([ \ \underline{1} \ 1 \ 3 \ 3 \ 7 \ \underline{3} \ ]\)
Теперь создадим копию первого массива:
\([ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]\), \([ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]\) и \([ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]\)
Поменяем местами элементы в первых двух копиях:
\([ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]\), \([ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]\) и \([ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]\).
В итоге за \(6\) действий получили массив, в котором все элементы одинаковые.
Можно доказать, что невозможно получить ответ меньше.