Олимпиадный тренинг

Задача . Modern Art 2


Picowso решила переключиться на 1-мерный стиль.
Теперь её картины могут описываться 1-мерным массивом цветов длины NN (1≤N≤100,000). А вот стиль у неё остался прежний: Он начинает на пустом отрезке и рисует отрезками. Она использует каждый из цветов 1…N ровно один раз, хотя некоторые из цветов могут быть полностью скрыты к концу рисования.
 
Moonet, соперник Picowso, придумал, как копировать картины Picowso. Он рисует множество не соединяющихся интервалов и т.д. Moonet может рисовать не более одного интервала каждого цвета во время всего процесса. Вычислите количество таких раундов, которые требуются Moonet, чтобы скопировать 1-мерную картину Picowso.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N, и следующие N строк содержат целое число в интервале 0…N, указывающее цвет каждой ячейки на 1-мерном холсте (0 для пустой ячейки).

ФОРМАТ ВЫВОДА:
 
Выведите минимальное количество раундов, которое требуется для копирования заданного рисунка или -1, если невозможно повторить этот рисунок стилем, аутеничным стилю Picowso (то есть, её нельзя нарисовать слоями последовательностей интервалов, по одному каждого цвета).
 
Ввод Вывод
7
0
1
4
5
1
3
3
2

 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя