题目描述

定义一个序列 $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)$。

输出格式

输出方案总数。

3
5 23 2021

4

5
0 0 1 3 3

15

10
0 1 2 3 4 5 6 7 8 9

20

提示

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