Competitions

# Divisible by 3

For an array [b1, b2, ..., bm] of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of bibj over 1i < jm.

You are given an array of n integers [a1, a2, ..., an], and are asked to find the number of pairs of integers (l, r) with 1lrn, for which the weight of the subarray [al, al+1, ..., ar] is divisible by 3.

#### Input

The first line contains a single integer n (1n5 * 105) - the length of the array.

The second line contains n integers a1, a2, ..., an (0ai109) - the elements of the array.

#### Output

Output a single integer - the number of pairs of integers (l, r) with 1lrn, for which the weight of the corresponding subarray is divisible by 3.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
5 23 2021

Output example #1
4

Input example #2
5
0 0 1 3 3

Output example #2
15

Input example #3
10
0 1 2 3 4 5 6 7 8 9

Output example #3
20

Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem E