Задача Q. Поле чудес ≡

Автор:Московская городская олимпиада по информатике 2003/04 г.   Ограничение времени:3 сек
Входной файл:e.in   Ограничение памяти:200 Мб
Выходной файл:e.out  

Условие

Для игры в "Поле чудес" используется круглый барабан, разделенный на сектора, и стрелка. В каждом секторе записано некоторое число. В различных секторах может быть записано одно и то же число.

Однажды ведущий решил изменить правила игры. Он сам стал вращать барабан и называть игроку (который барабана не видел) все числа подряд в том порядке, в котором на них указывала стрелка в процессе вращения барабана. Получилось так, что барабан сделал целое число оборотов, то есть последний сектор совпал с первым.

После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане? Напишите программу, отвечающую на этот вопрос.

Формат входного файла

Во входном файле записано сначала число N — количество чисел, которое назвал ведущий. Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале).

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 30000

Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.

Примеры тестов

№ Входной файл (e.in) Выходной файл (e.out)
1 
13
5 3 1 3 5 2 5 3 1 3 5 2 5
 
6
2 
4
1 1 1 1
 
1
3 
4
1 2 3 1
 
3
0.041s 0.011s 15