Đoạn con chia hết (Subarray Divisibility)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $n$ số nguyên

Hãy đếm số đoạn con liên tiếp không rỗng có tổng chia hết cho $n$.

Nói cách khác, cần đếm số cặp $(l,r)$ sao cho

và

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In số đoạn con có tổng chia hết cho $n$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le2\cdot10^5$

• $-10^9\le a_i\le10^9$

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: $n\le3000$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

5
3 1 2 7 4

Output

1

Giải thích

Với dãy

và $n=5$, đoạn $[2,4]$ có tổng

chia hết cho $5$. Không có đoạn nào khác thỏa điều kiện, nên đáp án là $1$.