Subarray Weight Divisibility by 3

Given an array a of length n, define the weight of a sequence b of length m as

\[ W(b)=\frac{1}{2}\Biggl[\Bigl(\sum_{i=1}^{m} b_i\Bigr)^2-\sum_{i=1}^{m} b_i^2\Biggr] = \sum_{i=1}^{m}\sum_{j=1}^{i-1} b_i \times b_j. \]

Your task is to count the number of pairs (l,r) with 1 ≤ l ≤ r ≤ n such that the subarray [a_l, a_{l+1}, \ldots, a_r] has a weight that is divisible by 3.

Hint on Modulo Arithmetic: Note that for any integer x, when taken modulo 3 we have

• If x ≡ 0 (mod 3) then \(x^2 ≡ 0\) (mod 3).
• If x ≡ 1 or 2 (mod 3) then \(x^2 ≡ 1\) (mod 3).

Thus, for a subarray b with sum \(S = \sum b_i\) and with \(t\) being the count of elements b_i that are not divisible by 3 (so that \(b_i^2 \equiv 1\) mod 3), the weight will be divisible by 3 if and only if

[ S^2 \equiv t \pmod{3}. ]

In particular, observe that:

• If \(S \equiv 0\) (mod 3), then we require \(t \equiv 0\) (mod 3).
• If \(S \equiv 1\) or \(2\) (mod 3), then we require \(t \equiv 1\) (mod 3) because \(1^2 \equiv 1\) and \(2^2 \equiv 1\) (mod 3).

Count all subarrays for which this condition holds.

inputFormat

The first line contains a single integer n (the length of the array).

The second line contains n integers a_1, a_2, \ldots, a_n separated by spaces.

outputFormat

Output a single integer, representing the number of subarrays whose weight is divisible by 3.

sample

3
1 2 3

4