P10740 [SEERC 2020] Divisible by 3

定义一个序列 $b$ 的权重为 $\sum_{i=1}^n \sum_{j=1}^{i-1} b_i \times b_j$。 现在你有一个长度为 $n$ 的数组 $a$，求一共存在多少种 $(l,r)$ 使得 $1 \leq l \leq r \leq n$ 且 $[a_l, a_{l+1},\ldots,a_r]$ 的权重能被 $3$ 整除。

第一行一个整数 $n\ (1 \leq n \leq 5 \times 10^5)$。 然后 $n$ 个整数 $a_i\ (0 \leq a_i \leq 10^9)$。

输出方案总数。

对于第一个样例，存在 $[1,1]$、$[2,2]$、$[3,3]$、$[1,3]$ 共 $4$ 种方案。