Cho dãy số nguyên không âm \(a_1, a_2, ..., a_n\) đếm số dãy con liên tiếp từ \(l\) đến \(r\) (\(1\le l\le r\le n\)) thỏa mãn \(\sum_{l\le i < j \le r} a_i\times a_j\) chia hết cho 3.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1\le n \le 5\cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) (\(0\le a_i \le 10^9\)).

Output

• Ghi ra số dãy con thỏa mãn.

Example

3
5 23 2021

4

5
0 0 1 3 3

15

10
0 1 2 3 4 5 6 7 8 9

20