B. DnB

Имя входного файла:	dnb.in
Имя выходного файла:	dnb.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Многим из нас нравится слушать музыку работая за компьютером. Программист Вася во время работы постоянно включает и слушает электронную музыку жанра Drum 'n' Bass. Она ему позволяет сконцентрироваться на задачах и максимально быстро решить их.

После решения нескольких сотен задач на благо компании KTP SOLUTIONS Вася заинтересовался, как можно определять такого рода музыку. Первое, что пришло в голову Васе – мелодия DnB состоит из повторяющихся кусочков звуков. Однако, он понял, что это не совсем верно, и уточнил определение.

Вася записывает мелодию в виде массива a из n чисел, в котором элемент a_i соответствует амплитуде колебания звука в i-ый момент времени.

Вася считает, что мелодия относится к жанру DnB, если её можно поделить на k отрезков одинаковой длины таких, что каждый отрезок является копией предыдущего с не более чем двумя измененными величинами колебания звука в некоторых моментах времени (при этом, отрезки звуков не должны быть полностью различны!).

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

В первой строке входного файла содержится целое число n – количество временных единиц, в которые известны амплитуды колебания (1 ≤ n ≤ 100'000). В следующей строке находится n целых чисел – описание мелодии в виде набора амплитуд колебания, i-ое из этих чисел a_i соответствует амплитуде колебания в i-ый момент времени (-10'000 ≤ a_i ≤ 10'000).

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

В выходной файл выведите "NO", если данная мелодия не является мелодией жанра DnB, иначе выведите "YES" и в следующей строке количество k отрезков, на которые мелодию надо разделить (2 ≤ k < n). Если существует несколько значений k, которые относят мелодию к жанру DnB, выведите любое из них.

Пример:

dnb.in	dnb.out
18 1 2 1 2 1 3 2 3 2 3 2 3 3 3 3 2 1 2	YES 9
10 1 2 3 4 5 6 7 8 9 10	NO

Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 2013-2014 учебный год

Обсудить       Отправить решение