文件名：num.in num.out

题目描述

小田得到了一个由 $n$ 个整数组成的数组 $a$，现在他可以对对数组进行如下操作：

• 选择一对 $(i, j)$，必须满足 $1 \le i \lt j \le n$，并且 $a_{i} == a_{j}$，然后将 $[a_{i}, a_{i+1}, ..., a_{j-1}, a_{j}]$ 这些数字全部从数组中删除。易知，删除后数组将变成 $[a_{1}, a_{2}, ..., a_{i-1}, a_{j+1}, ..., a_{n-1}, a_{n}]$ 。

现在小田通过若干次上述操作，将数组中的元素全部删除，请问他最少需要多少次操作呢？

输入描述

输入包含两行。

第一行一个正整数 $n$，表示数组的长度。

第二行输入 $n$ 个整数 $a_{i}$，数字之间用空格隔开。

输出描述

输出包含一行一个整数，表示最少的操作次数。

如果无论如何都无法使数组变为空，那么输出 -1 。

输入输出样例

输入 #1

5
0 1 0 1 1

输出 #1

2

输入 #2

5
1 1 1 1 0

输出 #2

-1

说明/提示

【样例 1 解释】

第一次操作选择 $i=1, j=3$，删除后数组变为 $[1, 1]$。

第二次操作选择 $i=1, j=2$，删除后数组变为空。

共两次。

【数据范围】

对于 $5 \%$ 的数据，有：$n = 1$ 。

对于 $15 \%$ 的数据，有：$n = 2$。

对于所有测试数据，有：$1 \le n \le 5 \times 10^{5}, 0 \le a_{i} \le 1$ 。