Делящийся на 3

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

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

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

Первая строка содержит одно число $n(1\le n\le 5\cdot 10^5)$ — длину массива.

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

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

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

Примеры