Modern Art 2#10528
Having grown bored with standard -dimensional artwork (and frustrated by others copying her work), the great bovine artist Picowso has decided to switch to a more minimalist, -dimensional style.
Although her paintings can now be represented by a -dimensional array of colors of length , her painting style remains unchanged: she starts with a blank canvas and layers a sequence of "rectangles" of paint onto it. In this -dimensional setting, these "rectangles" are simply intervals. She uses each of the colors exactly once, although, as before, some colors may end up being completely covered by the end.
To Picowso's great dismay, her competitor Moonet seems to have figured out how to copy even these -dimensional paintings, using a strategy similar to the one from 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. Moonet can paint at most one interval of each color during the entire process. Please compute the minimum number of rounds Moonet needs to copy a given -dimensional Picowso painting.
The first line contains n~(1 \le n \le 10^5), and the next lines contain an integer in the range , indicating the color of each cell in the -dimensional painting ( for a blank cell).
Print the minimum number of rounds needed to copy this painting, or if the painting could not have been an authentic work of Picowso (that is, if she could not have produced it by painting a sequence of intervals, using each color exactly once).
In this example, the interval of color must be painted in an earlier round than the intervals of colors and , so at least two rounds are needed.
Example 1