Bài toán: Đếm số đoạn con có tổng chia hết cho ~ n ~

Đề bài

Cho một mảng gồm ~ n ~ số nguyên, nhiệm vụ của bạn là đếm số đoạn con mà tổng các phần tử trong đoạn đó chia hết cho ~ n ~.

Input

• Dòng đầu tiên chứa một số nguyên ~ n ~: kích thước của mảng.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ a_1, a_2, \ldots, a_n ~: các phần tử của mảng.

Output

• In ra một số nguyên: số lượng đoạn con thỏa mãn điều kiện.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ -10^9 \leq a_i \leq 10^9 ~

Ví dụ

Input:

5
3 1 2 7 4

Output:

1

Giải thích:

• Đoạn con duy nhất có tổng chia hết cho ~ n = 5 ~ là ~ [3, 1, 2, 7, 4] ~.