Problem Description

Define the weight of a sequence $b$ as $\sum_{i=1}^n \sum_{j=1}^{i-1} b_i \times b_j$.

Now you are given an array $a$ of length $n$. Find how many pairs $(l, r)$ there are such that $1 \leq l \leq r \leq n$ and the weight of $[a_l, a_{l+1}, \ldots, a_r]$ is divisible by $3$.

Input Format

The first line contains an integer $n\ (1 \leq n \leq 5 \times 10^5)$.

Then follow $n$ integers $a_i\ (0 \leq a_i \leq 10^9)$.

Output Format

Output the total number of valid pairs.

3
5 23 2021

4

5
0 0 1 3 3

15

10
0 1 2 3 4 5 6 7 8 9

20

Hint

For the first sample, there are $4$ valid choices: $[1,1]$, $[2,2]$, $[3,3]$, and $[1,3]$.

Translated by ChatGPT 5