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 $n$ 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 $3$. \InputFile 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 $n$ integers $a_1, a_2, ..., a_n~(0 \le a_i \le 10^9)$ --- the elements of the array. \OutputFile 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 $3$.