You are given a circle of numbers (it is guaranteed that the sum of all numbers will always be larger than zero), and as long as there is a negative number among them, you can perform the following operation:
Choose a negative number Y , and then change the adjacent two numbers, X and Z , to X + Y and Z + Y respectively, and after that you can change the negative number Y to a positive number - Y .
The game terminates when no negative number can be found. Since you want to play the game as long as possible, you wonder how to play the game so that the total number of operations will be maximized, or whether there's a way to make this game such that this game never terminate.
There are multiple test cases in the input file. Each test case starts with one integer N (3<=N<=1000) , followed by N integers in the range [-1000, 1000] on the next line, describing the numbers on the circle in the clockwise direction. Two successive inputs are separated by a blank line. A single line with N = 0 indicates the end of input file.
For each test case, output one integer on a separate line, the maximum number of possible operations, the output format should be as indicated in the sample output. If a sequence of operations exists satisfying the condition that the game will never terminate, output ``-1" instead.