Với một mảng $[b_1, b_2, \dots, b_m]$ gồm các số nguyên, ta định nghĩa trọng số của nó là tổng các tích từng đôi một của các phần tử, cụ thể là tổng của $b_i b_j$ với $1 \le i < j \le m$.

Bạn được cho một mảng gồm $n$ số nguyên $[a_1, a_2, \dots, a_n]$, và được yêu cầu tìm số lượng các cặp số nguyên $(l, r)$ với $1 \le l \le r \le n$, sao cho trọng số của mảng con $[a_l, a_{l+1}, \dots, a_r]$ chia hết cho 3.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1 \le n \le 5 \cdot 10^5$) — độ dài của mảng.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — các phần tử của mảng.

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng các cặp số nguyên $(l, r)$ với $1 \le l \le r \le n$, sao cho trọng số của mảng con tương ứng chia hết cho 3.

Ví dụ

Dữ liệu vào 1

3
5 23 2021

Dữ liệu ra 1

4

Dữ liệu vào 2

5
0 0 1 3 3

Dữ liệu ra 2

15

Dữ liệu vào 3

10
0 1 2 3 4 5 6 7 8 9

Dữ liệu ra 3

20

Ghi chú

Trong ví dụ đầu tiên, trọng số của đúng 4 mảng con chia hết cho 3:

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