Современное искусство 2

Picowso решила переключиться на 1-мерный стиль.

Теперь её картины могут описываться 1-мерным массивом цветов длины n. А вот стиль у неё остался прежний: Он начинает на пустом отрезке и рисует отрезками. Она использует каждый из цветов 1 .. n ровно один раз, хотя некоторые из цветов могут быть полностью скрыты к концу рисования.

Moonet, соперник Picowso, придумал, как копировать картины Picowso. Он рисует множество не соединяющихся интервалов и т.д. Moonet может рисовать не более одного интервала каждого цвета во время всего процесса. Вычислите количество таких раундов, которые требуются Moonet, чтобы скопировать 1-мерную картину Picowso.

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

Первая строка содержит n (1 ≤ n ≤ 10^5), и следующие n строк содержат целое число в интервале 0 .. n, указывающее цвет каждой ячейки на 1-мерном холсте (0 для пустой ячейки).

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

Выведите минимальное количество раундов, которое требуется для копирования заданного рисунка или -1, если невозможно повторить этот рисунок стилем, аутеничным стилю Picowso (то есть, её нельзя нарисовать слоями последовательностей интервалов, по одному каждого цвета).

Примеры

Примечание

В этом примере интервал цвета 1 должен быть нарисован раньше раундов для цветов 4 и 5, поэтому требуется как минимум 2 раунда.