Divisible by 3

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$.

Input

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.

Output

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$.

Examples