Ensure Non-Zero Load Sum

You may only insert arbitrary integers into the original array; original elements cannot be deleted or changed. Make the sum of every non-empty contiguous segment nonzero, and find the minimum number of insertions. If the original array contains 0, the single-element zero segment cannot be eliminated, and this site's convention is to output −1 for no solution.

输入格式

The first line contains n, and the second line contains n integers. This site sets 1≤n≤200000 and elements in −10^9..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

5
1 -5 3 2 -5

输出：

1

样例 2

输入：

4
1 -1 1 -1

输出：

3

样例 3

输入：

2
0 1

输出：

-1

样例说明

Example 1: inserting 100 after 3 leaves no zero-sum segment, so at least one insertion is needed; the answer is 1. Example 2: every adjacent pair of opposite signs sums to 0, so one insertion is needed in each of the three gaps; the answer is 3. Example 3: the original element 0 is always a zero-sum single-element segment, so there is no solution: −1.