Problem Statement

Alex has an array containing integer elements. He wants it to be pretty. An array will be considered pretty if and only if the sum of every subsegment is non-zero . Alex can perform the following operation any number of times on the array: Insert an integer at any position in the array, including the first and last positions. Alex wants to know the minimum number of times the operation needs to be performed to make his array pretty. A subsegment of an array is a consecutive segment of elements in the array. Input Format The first line contains an integer n , denoting the size of array a . The following n lines denote array elements a i . Constraints 1 <= n <= 10 5 -10 9 <= a i <= 10 9 Output Format Return an integer denoting the minimum number of times the operation needs to be performed to make the array pretty. Sample Input 3 1 -2 2 Sample Output 1 Explanation Given an array [1, -2, 2], whose subsegment [-2, 2] has a zero sum, this array is not pretty initially. It means