[Usaco2017 Open]Modern Art 2

时间限制：10s 空间限制：128MB

题目描述

Having become bored with standard 2-dimensional artwork (and also frustrated at others copying her w

ork), the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional styl

e.Although, her paintings can now be described by a 1-dimensional array of colors of length N(1≤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. Sheuses ea

ch of the colors 1…Nexactly once, although just as before, some colors might end up being completel

y covered up by the end.To Picowso's great dismay, her competitor Moonet seems to have figured out h

ow to copy even these 1-dimensional paintings, using a similar strategy to the preceding problem: Mo

onet will paint a set ofdisjoint 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 proce

ss. Please compute thenumber of such rounds needed for Moonet to copy a given 1-dimensional Picowso

painting.

给定一个序列，序列上每个点有一个颜色。每一轮可以选择一些没有交集的区间，将每个区间涂上一种颜色。要求

全程每个颜色最多被涂一个区间，求最少涂多少轮

输入格式

The first line of input contains N

, and the next N lines contain an integer in the range 0…N

indicating the color of each cell in the 1-dimensional painting (0 for a blank cell).

输出格式

Please output the minimum number of rounds needed to copy this painting, or -1 if this could not hav

e possibly been an authentic work of Picowso (i.e., if she could not have painted it using a layered

sequence of intervals, one of each color).

样例输入

样例输出

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

提示

没有写明提示

题目来源

Gold