The problem statement goes as follows:

For an array $$$[b_1, b_2, \dots, b_m]$$$ of integers, let's define its weight as the sum of the pairwise products of its elements, namely as the sum $$$b_ib_j$$$ over $$$1 \leq i < j \leq m.$$$

You are given an array of $$$n$$$ integers $$$[a_1, a_2, \dots, a_n]$$$, and are asked to find the number of pairs of integers $$$(l, r)$$$ with $$$1 \leq l \leq r \leq n$$$, for which the weight of the subarray $$$[a_l, a_{l + 1}, \dots, a_r]$$$ is divisible by $$$3.$$$

Constraints: $$$1 \leq n \leq 5 \cdot 10^5,\space 0 \leq a_i \leq 10^9.$$$

A friend gave me only a pic of this problem, and I unfortunately couldn't find any judge to submit it to.. Anyway, the best time complexity I could come up with is just a pretty obvious $$$O(n^2)$$$, then I tried a few approaches for a better complexity but didn't manage to get very far, so I would appreciate it if somebody could share a faster approach!