Furik and Rubik and Sub Array

All submissions for this problem are available.
Furik and Rubik are playing the game Sub array. This game is played over an array of integers, consisting of N elements.
In this game, Furik decides an integer that is equal to sum of some subarray of this array and Rubik wants to guess this number.
But, since Rubik is a busy man, he wants to know how many times in the worst case he will have to try to guess this number. You may assume he acts optimally, i.e. he doesn't call the same number twice, and calls only those numbers, that might have been decided by Furik, meaning, the sum of some or the other subarray.
Let's call the array b, subarray of the array a, if there are numbers l and r such, that b_{1} = a_{l} AND b_{2} = a_{l+1} AND ... b_{b} = a_{r}, where b is the length of the array b.
Input
The first line contains the positive integer N. The second line contains N positive integers, which are the elements of the array.
Output
Output a single line containing the answer to the problem.
Constraints
Test Files with Time Limit set to 2 seconds
1 ≤ N * S ≤ 10^{10}, where S is the sum of the elements in the array.
Test Files with Time Limit set to 4 seconds
1 ≤ N * S ≤ 4 * 10^{10}
Sample
Input 3 1 2 3 Output 4 Input 9 6 1 7 3 7 1 8 5 7 Output 28
Explanation
Test Case 1: Furik can decide one of the following numbers: 1, 2, 3, 5, 6. For example, let us assume Furik has decided 3. In the worst case, Rubik may call out 4 numbers, since there are only 5 such numbers.
Author:  sereja 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/FARASA 
Tags  fft hard july13 maths sereja 
Date Added:  7052013 
Time Limit:  2  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions