Para un arreglo $[b_1, b_2, \dots, b_m]$ de enteros, definamos su peso como la suma de los productos por pares de sus elementos, es decir, como la suma de $b_i b_j$ para $1 \le i < j \le m$.
Se le da un arreglo de $n$ enteros $[a_1, a_2, \dots, a_n]$, y se le pide encontrar el número de pares de enteros $(l, r)$ con $1 \le l \le r \le n$, para los cuales el peso del subarreglo $[a_l, a_{l+1}, \dots, a_r]$ es divisible por 3.
Entrada
La primera línea de la entrada contiene un único entero $n$ ($1 \le n \le 5 \cdot 10^5$) — la longitud del arreglo.
La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — los elementos del arreglo.
Salida
Imprima un único entero — el número de pares de enteros $(l, r)$ con $1 \le l \le r \le n$, para los cuales el peso del subarreglo correspondiente es divisible por 3.
Ejemplos
Entrada 1
3 5 23 2021
Salida 1
4
Nota
En el primer ejemplo, los pesos de exactamente 4 subarreglos son divisibles por 3:
- $\text{weight}([5]) = \text{weight}([23]) = \text{weight}([2021]) = 0$
- $\text{weight}([5, 23, 2021]) = 56703 = 3 \cdot 41 \cdot 461$
Entrada 2
5 0 0 1 3 3
Salida 2
15
Entrada 3
10 0 1 2 3 4 5 6 7 8 9
Salida 3
20