整数からなる配列 $[b_1, b_2, \dots, b_m]$ に対して、その要素のペアの積の総和、すなわち $1 \le i < j \le m$ を満たす $b_i b_j$ の総和をその配列の重み (weight) と定義します。

$n$ 個の整数からなる配列 $[a_1, a_2, \dots, a_n]$ が与えられます。部分配列 $[a_l, a_{l+1}, \dots, a_r]$ ($1 \le l \le r \le n$) の重みが 3 で割り切れるような整数の組 $(l, r)$ の個数を求めてください。

入力

入力の最初の行には、配列の長さを表す整数 $n$ ($1 \le n \le 5 \cdot 10^5$) が与えられます。 2 行目には、配列の要素を表す $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 つの整数として出力してください。

入出力例

入力 1

3
5 23 2021

出力 1

4

注記

最初の例では、以下の 4 つの部分配列の重みが 3 で割り切れます。

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

入力 2

5
0 0 1 3 3

出力 2

15

入力 3

10
0 1 2 3 4 5 6 7 8 9

出力 3

20