Dla tablicy $[b_1, b_2, \dots, b_m]$ liczb całkowitych zdefiniujmy jej wagę jako sumę iloczynów par jej elementów, czyli sumę $b_i b_j$ dla $1 \le i < j \le m$.

Dana jest tablica $n$ liczb całkowitych $[a_1, a_2, \dots, a_n]$. Należy znaleźć liczbę par liczb całkowitych $(l, r)$ takich, że $1 \le l \le r \le n$, dla których waga podtablicy $[a_l, a_{l+1}, \dots, a_r]$ jest podzielna przez 3.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 5 \cdot 10^5$) — długość tablicy.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — elementy tablicy.

Wyjście

Wypisz pojedynczą liczbę całkowitą — liczbę par liczb całkowitych $(l, r)$ takich, że $1 \le l \le r \le n$, dla których waga odpowiadającej podtablicy jest podzielna przez 3.

Przykład

Wejście 1

3
5 23 2021

Wyjście 1

4

Wejście 2

5
0 0 1 3 3

Wyjście 2

15

Wejście 3

10
0 1 2 3 4 5 6 7 8 9

Wyjście 3

20

Uwagi

W pierwszym przykładzie wagi dokładnie 4 podtablic są podzielne przez 3:

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