# 2020 SEERC

# Divisible by 3

For an array [`b`

, _{1}`b`

, ..., _{2}`b`

] of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of _{m}`b`

over _{i}b_{j}**1** ≤ **i** < **j** ≤ **m**.

You are given an array of **n** integers [`a`

, _{1}`a`

, ..., _{2}`a`

], and are asked to find the number of pairs of integers (_{n}**l**, **r**) with **1** ≤ **l** ≤ **r** ≤ **n**, for which the weight of the subarray [`a`

, _{l}`a`

, ..., _{l+1}`a`

] is divisible by _{r}**3**.

#### Input

The first line contains a single integer **n** (**1** ≤ **n** ≤ **5** * `10`

) - the length of the array.^{5}

The second line contains **n** integers `a`

, _{1}`a`

, ..., _{2}`a`

(_{n}**0** ≤ `a`

≤ _{i}`10`

) - the elements of the array.^{9}

#### Output

Output a single integer - the number of pairs of integers (**l**, **r**) with **1** ≤ **l** ≤ **r** ≤ **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