Для игры в "Поле чудес" используется круглый барабан, разделенный на сектора, и стрелка. В каждом секторе записано некоторое число. В различных секторах может быть записано одно и то же число.
Однажды ведущий решил изменить правила игры. Он сам стал вращать барабан и называть игроку (который барабана не видел) все числа подряд в том порядке, в котором на них указывала стрелка в процессе вращения барабана. Получилось так, что барабан сделал целое число оборотов, то есть последний сектор совпал с первым.
После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане? Напишите программу, отвечающую на этот вопрос.
Входные данные
Во входном файле записано сначала число N — количество чисел, которое назвал ведущий (2 ≤ N ≤ 30000). Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале). Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.
Выходные данные
Выведите минимальное число секторов, которое может быть на барабане.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
13
5 3 1 3 5 2 5 3 1 3 5 2 5
|
6
|
|
2
|
4
1 1 1 1
|
1
|