GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Tuesday 15 November 2022

[Solution] Zero-Sum Prefixes Codeforces Solution



C. Zero-Sum Prefixes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The score of an array v1,v2,,vn is defined as the number of indices i (1in) such that v1+v2++vi=0.

You are given an array a1,a2,,an of length n. You can perform the following operation multiple times:

  • select an index i (1in) such that ai=0;
  • then replace ai by an arbitrary integer.

What is the maximum possible score of a that can be obtained by performing a sequence of such operations?

Input

Each test contains multiple test cases. The first line contains a single integer t (1t104) — the number of test cases.

The first line of each test case contains one integer n (1n2105) — the length of the array a.

The second line of each test case contains n integers a1,a2,,an (109ai109) — array a.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, print the maximum possible score of the array a after performing a sequence of operations.


Note

In the first test case, it is optimal to change the value of a2 to 2 in one operation.

The resulting array a will be [2,2,1,1,0], with a score of 3:

  • a1+a2=22=0;
  • a1+a2+a3+a4=22+11=0;
  • a1+a2+a3+a4+a5=22+11+0=0.

In the second test case, it is optimal to change the value of a3 to 2000000000, giving us an array with a score of 1.

In the third test case, it is not necessary to perform any operations.

No comments:

Post a Comment