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≤ L ≤ R ≤ n)\) thỏa mãn tổng của các tích \(a_i×a_j (L≤i < j≤R )\) chia hết cho 3.

Input

• Dòng đầu tiên chứa số nguyên \(n(1 ≤ n ≤5.10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (0 ≤ a_i ≤ 10^9)\).

Output

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

Sample Input

3
5 23 2021

Sample Output

4