Array and Counting 2

양의 정수 $N$과 길이가 $N$인 수열 $A = [A_1, A_2, \cdots, A_{N}]$이 주어진다. 다음 조건을 만족하는 정수 순서쌍 $(l, r)$의 개수를 구하여라.

• $1 \leq l \leq r \leq N$.
• 부분 수열 $[A_l, A_{l + 1}, \cdots, A_r]$의 산술평균이 정수이다.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1 \ A_2 \ \cdots \ A_{N}$

첫째 줄에 정답을 출력한다.

• $1 \leq N \leq 200 \ 000$.
• $1 \leq A_i \leq 100$ ($1 \leq i \leq N$).