Description：

一块长条画布，每次只能涂一块，且同种颜色只能涂一次，旧颜料涂完一个单位时间后才能涂新颜料，问最少多长时间复制一个画布。

$1\le n \le 100000$

Solution：

既然一个颜料只能涂一次，那一定是从头涂到尾，也就是说这题涂的顺序是已经确定的，只要把它计算出来即可。计算的时候可以用栈从 $1$ 到 $n$ 扫过去，遇到一个块就压栈，到了一个颜色最后一个位置就弹栈，历史最高栈顶就是答案。

不合法的情况就是嵌套的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int col[MAXN];

int fi[MAXN],la[MAXN];

int s[MAXN],tp = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&col[i]);

	memset(fi,0x3f,sizeof(fi));

	memset(la,0xc0,sizeof(la));

	for(int i = 1;i <= n;++i)

	{

		fi[col[i]] = min(fi[col[i]],i);

		la[col[i]] = max(la[col[i]],i);

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		if(col[i] == 0)

		{

			if(tp != 0)

			{

				puts("-1");

				return 0;

			}

			continue;

		}

		if(fi[col[i]] == i)

		{

			if(tp > 0 && la[col[i]] > la[s[tp]])

			{

				puts("-1");

				return 0;

			}

			s[++tp] = col[i];

			ans = max(ans,tp);

		}

		if(la[col[i]] == i)

		{

			--tp;

		}

		if(la[col[i]] != i && fi[col[i]] != i && s[tp] != col[i])

		{

			puts("-1");

			return 0;

		}

	}

	cout << ans << endl;

	return 0;

}