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 \le N \le 10^5\)).
• Dòng thứ hai chứa N số nguyên \(A_i\) (\(-10^9 \le A_i \le 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

Ràng buộc & Subtasks