Имеется барабан, разделённый на сектора, на котором по кругу написаны целые числа. Числа не обязательно различны. Известно, что барабан прокрутили несколько полных оборотов, выписывая значения секторов.

Например, если на барабане находились числа 2 3 3 1, и барабан сделал 2 оборота, то будут выписаны числа 2 3 3 1 2 3 3 1. К сожалению, числа перемешались в случайном порядке. Ваша задача — определить, какое минимальное количество секторов мог иметь барабан.

Формат входных и выходных данных

В первой строке входных данных содержится целое число N (1 £ N £ 10⁵) — количество выписанных чисел.

В следующей строке содержится N целых чисел в интервале от 0 до 10⁹, разделённых пробелами — значения выписанных секторов.

Выведите одно искомое число — минимальное количество секторов, которое мог иметь барабан.

Пример

Входные данные	Выходные данные
8 3 2 3 2 1 3 3 1	4
3 1 1 1	1