Ділиться на 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$.

Приклади