對於一個整數陣列 $[b_1, b_2, \dots, b_m]$，我們定義其「權重」（weight）為其元素兩兩乘積之和，即 $\sum_{1 \le i < j \le m} b_i b_j$。

給定一個包含 $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$)，代表陣列的元素。

輸出格式

輸出一個整數，代表滿足子陣列權重能被 3 整除的整數對 $(l, r)$ ($1 \le l \le r \le n$) 的數量。

範例

輸入格式 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$