对于一个整数数组 $[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]$，请找出满足 $1 \le l \le r \le n$ 的整数对 $(l, r)$ 的数量，使得子数组 $[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$