eolymp
bolt
Try our new interface for solving problems
Problems

Листая "Песнь о Гайавате"

Листая "Песнь о Гайавате"

Time limit 2 seconds
Memory limit 256 MiB

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

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

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

Input data

В первой строке входного файла содержится натуральное число n, не превосходящее 100000, - количество глав "Песни о Гайавате".

В следующей строке содержаться n натуральных чисел, не превышающих n, - "самые внутренние" номера глав.

Output data

Выведите одно число - максимальную вложенность исходного списка, или -1, если такого списка не могло быть.

Examples

Input example #1
8
1 2 1 1 2 2 1 3
Output example #1
3