Для массива целых чисел $[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$. \InputFile Первая строка содержит одно число $n~(1 \le n \le 5 \cdot 10^5)$ --- длину массива. Вторая строка содержит $n$ целых чисел $a_1, a_2, ..., a_n~(0 \le a_i \le 10^9)$ --- элементы массива. \OutputFile Выведите одно целое число --- количество пар целых чисел $(l, r)$, где $1 \le l \le r \le n$, для которых вес соответствующего подмассива делится на $3$.