Темы --> Информатика --> Алгоритмы --> Алгоритмы на строках
    Суффиксный массив(2 задач)
    Z-функция, Префикс-функция(5 задач)
    Ахо-Корасик(2 задач)
---> 1 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников --> 10-11 классы
    2004(7 задач)
    2005(7 задач)
    2006(8 задач)
    2007(8 задач)
    2008(8 задач)
    2011(5 задач)
    2012(14 задач)
    2013(14 задач)
    2014(14 задач)
    2015(14 задач)
    2016(15 задач)
Страница: 1 Отображать по:
#998
Поле чудес
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Барабан совершает несколько оборотов. Дана последовательность чисел, на которые указывает стрелка. Требуется определить сколько всего чисел на барабане (найти максимальную подпоследовательносьть, из повторов которой состоит последовательность).

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

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

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

Входные данные

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

Выходные данные

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

Примеры
Входные данные
13
5 3 1 3 5 2 5 3 1 3 5 2 5
Выходные данные
6
Входные данные
4
1 1 1 1
Выходные данные
1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест