eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Листаючи "Пісню про Гайавату"

Листаючи "Пісню про Гайавату"

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Генрі Удосворт Логфелло, записуючи "Пісню про Гайавату", трохи спілкувався з Ромацколгатлем, шаманом історій. Окремі розділи, записані зі слів Ромацколгатля, Лонгфелло записував на портативну друкарську машинку, організовуючи їх у формі вкладених списків. А саме: розділи нумеруються натуральними числами, кожен розділ має вкладені розділи, які незалежно нумеруються натуральними числами, ті можуть мати вкладені розділи наступного рівня і так далі. Нумерація роділів, вкладених у один розділ, або розділів верхнього рівня вкладеності починається з одиниці и продовжується послідовними натуральними числами.

Генрі слід було б нумеровати вкладені списки, зберігаючи нумерацію зовнішніх списків (див. рисунок, ліворуч). Проте з метою економії чорнил та часу, заслухавшись розповідями Ромацколгатля, він записував лише номери у самих вкладених списках (див. рисунок праворуч).

Тепер, повернувшись з експедиції, Логфелло хоче вияснити, чи не помилився він, і яка могла бути максимально можлива глибина вкладеності списків (кількість рівнів вкладеності).

Вхідні дані

У першому рядку вхідного файлу міститься натуральне число n, яке не перевищує 100000, - кількість розділів "Пісні про Гайавату".

У наступному рядку містяться n натуральних чисел, які не перевищують n, - "самі внутрішні" номери розділів.

Вихідні дані

Виведите одне число - максимальну вкладеність початкового списку, або -1, якщо такого списку не могло бути.

Приклад

Вхідні дані #1
8
1 2 1 1 2 2 1 3
Вихідні дані #1
3