该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师得到了一个数组并获得了一个能力：如果一个长度大于1的区间首尾数字相同，则对可以去除这个区间，徐老师想知道他至少操作几次才能清空这个数组，如果不能则输出-1

Format

Input

第一行一个正整数$n(n \leq 10^5)$，表示数组长度

第二行n个整数$a_i(0 \leq a_i \leq 1)$，表示数组数值大小

Output

输出一个整数，表示最小的操作次数，不可能则输出-1

Samples

4
0 0 1 1

2

Limitation

1s, 1024KiB for each test case.