Dãy số

Cho một dãy \(A\) gồm \(n\) số nguyên dương \(A_1, A_2, A_3, ..., A_n\). Có bao nhiêu cặp chỉ số \((i,j)\) thỏa mãn \(1 \leq i < j \leq n\) để tổng \(A_i+A_j\) chia hết cho \(3\).

Input

Dữ liệu vào: Đọc từ tệp DAYSO.INP gồm \(2\) dòng:

• Dòng đầu tiên chứa số nguyên \(n\) \((2 \leq n \leq 10^5)\).
• Dòng thứ \(2\) chứa \(n\) số nguyên dương \(A_1, A_2, A_3, ..., A_n\), mỗi số không vượt quá \(10^9\), giữa hai số cách nhau \(1\) dấu cách.

Output

Kết quả: Ghi ra tệp DAYSO.OUT một dòng duy nhất là số cặp tìm được.

Example

7
3 1 2 9 5 3 5

6

Scoring

• Có \(70\%\) số điểm có \(n \leq 10^4\).
• Còn \(30\%\) số điểm còn lại không có ràng buộc gì thêm.