Листая "Песнь о Гайавате"
Листая "Песнь о Гайавате"
Генри Удосворт Логфелло, записывая "Песнь о Гайавате", много общался с Ромацколгатлем, шаманом историй. Отдельные главы, записанные со слов Ромацколгатля, Лонгфелло записывал на портативную пишущую машинку, организовывая их в форме вложенных списков. А именно: главы нумеруются натуральными числами, каждая глава имеет вложенные главы, которые независимо нумеруются натуральными числами, те могут иметь вложенные главы следующего уровня и так далее. Нумерация глав, вложенных в одну главу, либо глав верхнего уровня вложенности начинается с единицы и продолжается последовательными натуральными числами.
Генри следовало бы нумеровать вложенные списки, сохраняя нумерацию внешних списков (см. рисунок, слева). однако в целях экономии чернил и времени, заслушавшись сказаниями Ромацколгатля, он записывал только номера в самих вложенных списках (см. рисунок справа).
Теперь, вернувшись из экспедиции, Логфелло хочет выяснить, не ошибся ли он, и какова могла быть максимально возможная глубина вложенности списков (количество уровней вложенности).
Input data
В первой строке входного файла содержится натуральное число n, не превосходящее 100000, - количество глав "Песни о Гайавате".
В следующей строке содержаться n натуральных чисел, не превышающих n, - "самые внутренние" номера глав.
Output data
Выведите одно число - максимальную вложенность исходного списка, или -1, если такого списка не могло быть.
Examples
8 1 2 1 1 2 2 1 3
3