Modern Art 2

Bored with standard 2-dimensional artwork, and frustrated that others copy her work, the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional style.

Her paintings can now be described by a 1-dimensional array of colors of length $N$ ($1 \leq N \leq 100\,000$), but her painting style is unchanged. She starts with a blank canvas and layers on it a sequence of "rectangles" of paint, which in this 1-dimensional case are simply intervals. She uses each of the colors $1, 2, \ldots, N$ exactly once, although, just as before, some colors might end up completely covered by the end.

To Picowso's dismay, her competitor Moonet seems to have figured out how to copy even these 1-dimensional paintings, using a strategy similar to the one in the preceding problem. Moonet paints a set of disjoint intervals, waits for them to dry, then paints another set of disjoint intervals, and so on. Each paint-and-dry step is one round. Over the entire process, Moonet can paint at most one interval of each color.

Given a 1-dimensional Picowso painting, compute the number of rounds Moonet needs to copy it.

The first line contains $N$. Each of the next $N$ lines contains an integer from $0$ to $N$ inclusive, the color of one cell of the 1-dimensional painting, in order. The value $0$ marks a blank cell.

Print the minimum number of rounds needed to copy this painting. If it could not be an authentic Picowso, that is, if she could not have painted it by layering a sequence of intervals with one interval of each color, print $-1$.

In the example, the interval of color $1$ must be painted in an earlier round than the intervals of colors $4$ and $5$, so at least two rounds are needed.