Divisible by 3#10884
For an array [b_1, b_2, ..., b_m] of integers, let's define its weight as the sum of pairwise products of its elements, namely as the sum of b_i \cdot b_j over 1 \le i < j \le m.
You are given an array of integers [a_1, a_2, ..., 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}, ..., a_r] is divisible by .
The first line contains a single integer n~(1 \le n \le 5 \cdot 10^5) — the length of the array.
The second line contains integers a_1, a_2, ..., 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 .
Example 1
Example 2
Example 3