题目描述

$n$ 个数 $a_1,a_2,...,a_n$ 围成一圈，$a_1$ 和 $a_n$ 相邻。每一次操作选择 $a_i$，变成 $-a_i$ ，并把相邻的两个数加上 $a_i$。求最少经过几次操作，让所有数都变为非负整数。

输入格式

有多组数据。

每组数据，一行一个正整数 $n$，第二行 $n$ 个整数 $a_i$。

当 $n=0$ 时，输入结束。

输出格式

对于每组数据，输出一个整数表示最少次数，若永远无法满足要求输出 $-1$。

样例

样例输入

3
2 3 3
4
-1 2 -2 2
8
-1 -1 -2 -2 1 1 1 2
4
1 2 -2 2
0

样例输出

0
5
-1
1

数据范围

• $2 \le n \le 1000$
• $|a_i| \le 10^5$ $|\sum{}^{} a_i| \le 10$

咋做呀喵，求代码/原题，完全没思路喵。。。

给5关，思路不行的喵，急急急了，求助！！！