You are given an integer array C (the graceful constraints, illustrated later).
A sequence of real numbers that satisfies the following conditions is considered "graceful":
For each C[i] in C:
If C[i] is negative, the condition is: "The sum of every consecutive -C[i] terms in the sequence must be negative."
If C[i] is positive, the condition is: "The sum of every consecutive C[i] terms in the sequence must be positive."
Find the maximum length possible for a graceful sequence. If there exists an infinitely long fraceful sequence that satisfies all the conditions, print -1.
On the first line of input file, an integer T indicates the number of testcases.
Following is T lines of testcases. Each testcase in a line contains precisely the array C.
all number in C is bigger than -1001 and smaller than 1001 and not equal to 0.
All elements in C will be pairwise distinct.
C will contain between 1 and 50 elements, inclusive.
For each testcase, output an integer representing the maximum possible length of a valid sequence under the constraint given.
3 -2 3 524 1 -1
3 -1 0
For sample input 1, the sequence 2, -3, 2 satisfies all the conditions and its length is 3.
It can be proved that there is no valid sequence with more terms.
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|