Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con trong đó tổng các giá trị chia hết cho \(n\).

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.

Output

• In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(-10^9 \leq a_i \leq 10^9\)

Example

5
3 1 2 7 4

1