print1958. Барабан

printБарабан

Ограничения: время – 300ms/600ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Имеется барабан, разделённый на сектора, на котором по кругу написаны целые числа. Числа не обязательно различны. Известно, что барабан прокрутили несколько полных оборотов, выписывая значения секторов.
Например, если на барабане находились числа 2 3 3 1, и барабан сделал 2 оборота, то будут выписаны числа 2 3 3 1 2 3 3 1. К сожалению, числа перемешались в случайном порядке. Ваша задача — определить, какое минимальное количество секторов мог иметь барабан.
В первой строке входного файла содержится целое число `N` (`1\ ≤\ N\ ≤\ 10^5`) — количество выписанных чисел. В следующей строке содержится `N` целых чисел в интервале от 0 до `10^9`, разделённых пробелами — значения выписанных секторов.
Выведите в выходной файл одно искомое число — минимальное количество секторов, которое мог иметь барабан.

Пример ввода 1

8
3 2 3 2 1 3 3 1

Пример вывода 1

4

Пример ввода 2

3
1 1 1

Пример вывода 2

1
Источник: XVI межвузовская олимпиада по программированию, Вологда, 2013
loading