8159: Modern Art 2

Although, her paintings can now be described by a 1-dimensional array of colors of length NN (1≤N≤100,0001≤N≤100,000), her painting style remains unchanged: she starts with a blank canvas and layers upon it a sequence of "rectangles" of paint, which in this 1-dimensional case are simply intervals. She uses each of the colors 1…N1…N exactly once, although just as before, some colors might end up being completely covered up by the end.

To Picowso's great dismay, her competitor Moonet seems to have figured out how to copy even these 1-dimensional paintings, using a similar strategy to the preceding problem: Moonet will paint a set of disjoint intervals, wait for them to dry, then paint another set of disjoint intervals, and so on. Moonet can only paint at most one interval of each color over the entire process. Please compute the number of such rounds needed for Moonet to copy a given 1-dimensional Picowso painting.

现在给你一个长度为N(N≤1e5)的画条

上面有若干种颜色，每位的数字表示一种颜色，0表示没有涂色

为了快捷，每次涂色可以用一种颜色填充一个区间，同一种颜色只能使用一次

每次可以涂色好几次，但是这些区间必须分别连续切两两不能相交

然后等待1day油漆干了后再同样操作，输出创作完成并全干了后的最少时间

7
0
1
4
5
1
3
3

2