21909번 - Divisible by 3 다국어

문제

For an array $[b_1, b_2, \dots , b_m]$ of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of $b_ib_j$ over 1ドル \le i < j \le m$.

You are given an array of $n$ integers $[a_1, a_2, \dots , a_n],ドル and are asked to find the number of pairs of integers $(l, r)$ with 1ドル \le l \le r \le n,ドル for which the weight of the subarray $[a_l, a_{l+1}, \dots , a_r]$ is divisible by 3ドル$.

입력

The first line of the input contains a single integer $n$ (1ドル \le n \le 5 \cdot 10^5$) — the length of the array.

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ (0ドル \le a_i \le 10^9$) — the elements of the array.

출력

Output a single integer — the number of pairs of integers $(l, r)$ with 1ドル \le l \le r \le n,ドル for which the weight of the corresponding subarray is divisible by 3ドル$.

제한

힌트

In the first sample, the weights of exactly 4ドル$ subarrays are divisible by 3ドル$:

• weight($[5]$) = weight($[23]$) = weight($[2021]$) = 0ドル$
• weight($[5, 23, 2021]$) = 56703ドル$ = 3ドル \cdot 41 \cdot 461$