Problem Description

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

Given an array \( a \) of length \( n \), find the total number of pairs \( (l, r) \) such that \( 1 \leq l \leq r \leq n \) and the weight of the subarray \( [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) \).

The next line contains \( n \) integers \( a_i \) \( (0 \leq a_i \leq 10^9) \).

Output Format

Output the total number of such pairs \( (l, r) \).

Sample Input and Output

Sample Input #1

3
5 23 2021

Sample Output #1

4

Sample Input #2

5
0 0 1 3 3

Sample Output #2

15

Sample Input #3

10
0 1 2 3 4 5 6 7 8 9

Sample Output #3

20

Notes

For the first sample, there are 4 valid pairs: \( [1,1] \), \( [2,2] \), \( [3,3] \), and \( [1,3] \).

见题面 Input 部分

见题面 Output 部分