Cho mảng A gồm N số nguyên. Hãy đếm số lượng đoạn con liên tiếp có tổng bằng 0.

Sử dụng prefix sum kết hợp hash map: tính tổng tiền tố pref[i] = A[0] + ... + A[i-1]. Hai tổng tiền tố bằng nhau (pref[l] = pref[r]) nghĩa là đoạn (l, r-1] có tổng bằng 0. Dùng hash map đếm số lần xuất hiện của mỗi giá trị prefix.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 10^5).
• Dòng thứ hai chứa N số nguyên A_i (-10^9 ≤ A_i ≤ 10^9).

Đầu ra

Một số nguyên duy nhất là số lượng đoạn con có tổng bằng 0.

Ví dụ

Input:
6
1 -1 2 -2 3 -3

Output:
6