Cho dãy \(N\) số nguyên dương \(a_i\). Đếm số cách chia dãy đã cho thành các đoạn liên tiếp sao cho tổng các phần tử mỗi đoạn từ đoạn thứ hai trở đi thì bằng nhau.

Input

• Dòng đầu tiên chứa \(N (1≤N≤2*10^5)\)

• Dòng thứ hai chứa \(N\) số \(a_i (1≤a_i≤4*10^5,a_1+a_2+...+a_N≤4*10^5 ).\)

Output

• Đưa ra số cách chia.

Sample Input

5
1 1 2 1 1

Sample Output

6