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$$$:
Name |
---|