Informatica Online Judge

  G수열 [0494 / 01EE]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 40   Total Tried : 47


The Champion of this Problem (C++) : gs15120 - 212ms / 1757byte
My Best Submission (C++) : N/A

[]

Background

수열 A0, A1, ... , An-1이 주어진다. “돌린다” 라는 것은 첫 번째 수를 마지막 자리로 옮기는 것을 의미한다. 한번 돌리면 A1, A2, ... , An-1, A0의 수열이 되고, 처음 수열에서 k번 돌리게 되면 Ak, Ak+1, .... An, A1, ... , Ak-1의 새로운 수열이 만들어 진다.

수열 B0, B1, ... , Bn-1에서 G수열이 되기 위한 조건은 첫 번째 수부터 i번째 수까지 까지 더한 값에 음수가 없어야 한다. 즉, B0+B1+... +Bi >= 0 (0<=i<=n-1)을 만족해야 한다.

입력으로 주어진 수열을 G수열이 되게 하는 돌리기는 몇 가지 인지 구하시오.

Input

테스트 케이스 T가 주어지고 다음 줄부터 N(1,000,000이하의 자연수)과 N개의 정수가 T번 입력된다. 각 정수의 절댓값은 1000을 넘지 않는다.

Output

T개의 한 줄에 한 개씩 출력한다. 이 정수는 G수열이 되게 하는 돌리기 개수이다.

IO Example

입력
3
1
2
4
5 -3 5 4
5
0 4 -5 -3 -3

출력
1
3
0

출제:김태양(GSHS Im a Coder 1기 조교)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]