当前没有测试数据。

题目描述

在《僵尸大战植物》游戏中，你扮演的是一只僵尸。在你面前的道路上有 $n$ 个连续的格子，依次编号为 $1$ 到 $n$。每个格子上都长着一株植物，有可能是向日葵（用 $1$ 表示），也有可能是土豆地雷（用 $0$ 表示）。你需要依次走过这些格子，当碰见向日葵时你会立即把它吃掉，并获得一个大脑（我们不妨假设向日葵有大脑），此时并不会阻碍你前进的步伐；但如果碰到了土豆地雷，则你会立刻被炸死。

幸运的是，你得到了僵王博士赐予的高科技穿梭器。使用一次穿梭器，你可以从任何一个向日葵的位置穿越到前方另一个向日葵的位置。但穿梭器十分珍贵，你最多只有一次使用机会，并且需要在使用之前支付一定的代价。具体为：若你准备使用穿梭器前进 $x$ 个格子，则需要支付 $x$ 个大脑。若你没有足够的大脑，则无法启动穿梭器。

大脑是你的食物，如果支付了过多的大脑，你此后的生活也会非常艰难。因此现在来到了性命攸关的抉择时刻，请你慎重抉择，然后计算出：为了活着抵达终点，你最少需要支付多少个大脑。

你也可以不使用穿梭器，这样你支付的大脑数量为 $0$。当然，有时你也不得不感叹造化弄人，如果无论如何都无法活着抵达终点，你只能认命，并祈求下辈子不要当僵尸。

题目数据保证：第一个格子和最后一个格子一定是向日葵。

输入格式

第一行：一个整数 $n$，表示格子总数；

第二行：$n$ 个整数 $a_1,a_2,...,a_n$，分别表示每个格子上的植物。

输出格式

一个整数，表示需要支付的大脑数量的最小值。若不存在活着抵达终点的方案，则输出 $-1$。

样例数据

3
1 1 1

0

5
1 0 1 0 1

-1

8
1 1 1 0 1 0 1 1

3

样例解释

在第一组样例中，并不需要使用穿梭器就可以活着抵达终点，因此输出 $0$。

在第二组样例中，很显然无论如何都不能活着抵达终点，因此输出 $-1$。

在第三组样例中，可以在走完前三个格子后（此时拥有 $3$ 个大脑）使用穿梭器，向后穿梭三个格子，直接抵达第 $7$ 个格子，此时需要支付 $3$ 个大脑。

数据范围

对于所有数据，$1≤t≤100；2≤n≤100；0≤a_i≤1；a_1=a_n=1$。