408341: GYM103102 E Divisible by 3

For an array $$$[b_1, b_2, \ldots, 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, \ldots, 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}, \ldots , 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, \ldots, 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$$$.

3
5 23 2021

4

5
0 0 1 3 3

15

10
0 1 2 3 4 5 6 7 8 9

20

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

• $$$\text{weight}([5]) = \text{weight}([23]) = \text{weight}([2021]) = 0$$$
• $$$\text{weight}([5, 23, 2021]) = 56703 = 3 \cdot 41 \cdot 461$$$