Dãy số

Cho một dãy số \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, a_3, ...,a_n\). Đếm xem có bao nhiêu cặp số \((a_i, a_j)\) thỏa mãn \((1 \leq i, j \leq n, i \neq j)\) và 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 dương \(n\) \((2 \leq n \leq 10^5)\).
• Dòng thứ hai 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 các số cách nhau một dấu cách trống.

Output

Dữ liệu ra: Ghi vào tệp DAYSO.OUT một số duy nhất là kết quả tìm được.

Example

7
3 1 2 9 5 3 5

6

Scoring

• Có \(70\%\) số test ứng với \(70\%\) số điểm của bài có \(n \leq 10^4\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm với trường hợp còn lại.