Question

You are given an array A which consists of N integers.

Find the total number of unique subarray sum that are possible in A.

Note:

A subarray is a contiguous part of an array.

Input Format

The first line contains an integer, N, denoting the number of elements in A.

Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer

describing A[1]

Constraints

1<= N <= 10^5

Sample Test Cases

Case 1

Input

5

7

2

3

2

2

Output: 9

Explanation:

Given N = 5, A [7, 2, 3, 2, 2]

The number of unique sums that can be obtained by taking the sum of elements in

all possible subarrays of A are 9 which are [7], [9], [12], [14], [2], [5], [3], [4], [16].

Case 2

Input:

5

4

10

5

2

2

Output:

12

Explanation:

Given N = 5, A [4, 10, 5, 2, 2]

The number of unique sums that can be obtained by taking the sum of elements in

all possible subarrays of A are 12.

Case 3

Input:

5

2

10

3

4

2

Output:

13

def solve(N,A)

Answer 1

def solve(N, A):
 unique_sums = set()
 
 for start in range(N):
 current_sum = 0
 for end in range(start, N):
 current_sum += A[end]
 unique_sums.add(current_sum)
 
 print(len(unique_sums))