We consider the correspondence between a resulting integer sequence with a sequence of operations. In order to make a non-empty sequence, we may take the following greedy approach: repeat adding the 1st and the 2nd leftmost values until the 1st value of the desired sequence is obtained, then repeat adding the 2nd and the 3rd leftmost values until the 2nd value of the desired sequence is obtained, \(\cdots\), and so on. A suffix of \(A\) that does not correspond to any element of the desired sequence may remain, but in that case, the desired sequence can be obtained if and only if the sum of elements in the suffix is \(0\). Since the sequence of operations in this greedy method and the resulting array correspond one-by-one, so it is sufficient to find the number of possible sequences of operations.

We use DP (Dynamic Programming). Let \(DP[i]\) be the number of suffixes of sequences of operations of the greedy algorithm such that the first \(i\) elements of \(A\) correspond to the elements of desired sequence. Then, for the maximum \(j(<i)\) such that \(A[j]+A[j+1]+ \cdots +A[i]=0\), it holds that \(DP[i]=DP[j]+DP[j+1]+ \cdots + DP[i-1]\). For each \(k(<j)\), the sum of elements from \(A[k]\) through \(A[j-1]\) is equal to that of \(A[k]\) through \(A[i]\), and in the greedy algorithm the former correspond to an element, so there is no transition from \(DP[i]\) to \(DP[k]\).

In order to find \(j\), compute the cumulative sums of \(A\) from the left, and for each cumulative sum manage the largest index less than \(i\) with a data structure like a map. Also, compute the cumulative sums of \(DP\) from the left so as to find \(DP[i]\) in an \(O(1)\) time each.

The answer is the sum of \(DP[k]\) for \(k(>0)\) such that \(A[k]+A[k+1]+ \cdots +A[N]=0\). The total time complexity is \(O(NlogN)\) or \(O(N)\).