Для массива $[b_1, b_2, \dots, b_m]$ целых чисел определим его вес как сумму попарных произведений его элементов, а именно как сумму $b_i b_j$ для всех $1 \le i < j \le m$.

Вам дан массив из $n$ целых чисел $[a_1, a_2, \dots, a_n]$. Требуется найти количество пар целых чисел $(l, r)$, где $1 \le l \le r \le n$, таких, что вес подмассива $[a_l, a_{l+1}, \dots, a_r]$ делится на 3.

Входные данные

Первая строка содержит единственное целое число $n$ ($1 \le n \le 5 \cdot 10^5$) — длину массива. Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — элементы массива.

Выходные данные

Выведите единственное целое число — количество пар целых чисел $(l, r)$ с $1 \le l \le r \le n$, для которых вес соответствующего подмассива делится на 3.

Примеры

Входные данные 1

3
5 23 2021

Выходные данные 1

4

Входные данные 2

5
0 0 1 3 3

Выходные данные 2

15

Входные данные 3

10
0 1 2 3 4 5 6 7 8 9

Выходные данные 3

20

Примечание

В первом примере веса ровно 4 подмассивов делятся на 3:

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