eolymp
Competitions

2020 SEERC

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