Pour un tableau $[b_1, b_2, \dots, b_m]$ d'entiers, définissons son poids comme la somme des produits par paires de ses éléments, c'est-à-dire la somme des $b_i b_j$ pour $1 \le i < j \le m$.

Vous disposez d'un tableau de $n$ entiers $[a_1, a_2, \dots, a_n]$, et vous devez trouver le nombre de paires d'entiers $(l, r)$ avec $1 \le l \le r \le n$, pour lesquelles le poids du sous-tableau $[a_l, a_{l+1}, \dots, a_r]$ est divisible par 3.

Entrée

La première ligne de l'entrée contient un entier unique $n$ ($1 \le n \le 5 \cdot 10^5$) — la longueur du tableau. La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — les éléments du tableau.

Sortie

Affichez un entier unique — le nombre de paires d'entiers $(l, r)$ avec $1 \le l \le r \le n$, pour lesquelles le poids du sous-tableau correspondant est divisible par 3.

Exemples

Entrée 1

3
5 23 2021

Sortie 1

4

Entrée 2

5
0 0 1 3 3

Sortie 2

15

Entrée 3

10
0 1 2 3 4 5 6 7 8 9

Sortie 3

20

Remarque

Dans le premier exemple, les poids de exactement 4 sous-tableaux sont divisibles par 3 :

• $\text{weight}([5]) = \text{weight}([23]) = \text{weight}([2021]) = 0$
• $\text{weight}([5, 23, 2021]) = 56703 = 3 \cdot 41 \cdot 461$