附加文件

题目描述

windy有一条木板需要被粉刷。这条木板被分为 N 个格子。第 i 个格子要被刷成颜色 Ci （0 ≤ Ci ≤ 10^5 ，若 Ci = 0 表示该格子要保留木板原色，不要被粉刷）。

windy的粉刷分为若干天。每天可以选择木板上任意多个不重叠的区间（每个区间由连续的若干个格子组成）进行粉刷，并且每个区间粉刷的颜色互不相同。

同一天每个格子最多只能被粉刷一次。

如果某个格子之前被粉刷过，则再次粉刷时会覆盖之前的颜色。

由于颜色调配非常麻烦，所以在整个工期内，任意一种颜色只会调配一次，即只能在一个区间内使用一次。

如果windy要把全部格子粉刷成指定颜色，他最少需要多少天完成？如果无法完成任务，则输出 -1。

输入格式

第一行包含一个整数 N

接下来有 N 行，每行一个整数 Ci

输出格式

包含一个整数，表示最少天数；如果无法完成任务，则输出 -1

样例1输入

8
0
1
3
5
1
0
2
2

样例1输出

2

样例1解释

初始：

0 0 0 0 0 0 0 0

第一天粉刷后：

0 1 1 1 1 0 2 2

第二天粉刷后：

0 1 3 5 1 0 2 2

样例2输入

8
0
1
3
0
1
0
2
2

样例2输出

-1

数据范围

100%的数据，满足 1 ≤ N ≤ 10^5 。