Flipping through "The Song of Hiawatha"
Henry Wadsworth Longfellow, while writing "The Song of Hiawatha," had some interactions with Romatskolgatl, the shaman of stories. Certain sections, transcribed from Romatskolgatl's words, were typed by Longfellow on a portable typewriter, organizing them into nested lists. Each section is numbered with natural numbers, and each section can contain nested subsections, also independently numbered with natural numbers. These subsections can further contain their own nested sections, and so on. The numbering of sections nested within a single section, or sections at the top level of nesting, begins at one and continues with consecutive natural numbers.
Henry was supposed to number the nested lists while maintaining the numbering of the outer lists (see figure, left). However, to conserve ink and time, being engrossed in Romatskolgatl's stories, he recorded only the numbers in the innermost lists (see figure, right).
Now, upon returning from the expedition, Longfellow wants to check if he made any mistakes and determine the maximum possible depth of list nesting (the number of levels of nesting).
Input
The first line of the input file contains a natural number n, which does not exceed 100000, representing the number of sections in "The Song of Hiawatha."
The next line contains n natural numbers, each not exceeding n, representing the "innermost" section numbers.
Output
Output a single number: the maximum nesting depth of the original list, or -1 if such a list could not have existed.