Tài là học sinh giỏi toán và ham học hỏi. Tài rất thích thú với những cặp số đặc biệt. Cặp số đặc biệt là những cặp số có tổng chia hết cho \(3\).

Cho một dãy \(a\) gồm \(n\) số nguyên dương. Tài muốn biết trong dãy \(a\), có bao nhiêu cặp chỉ số \((i, j)\) với \((1 \le i < j \le n)\) sao cho tổng \(a_i + a_j\) chia hết cho \(3\).

Yêu cầu: Bạn hãy giúp bạn Tài đếm xem có bao nhiêu cặp số này nhé.

Input

• Dòng 1: Chứa số nguyên dương \(n\) (\(1 < n \le 10^5\)).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6, 1 \le i \le n\)). Các số cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất là số lượng cặp số của dãy \(a\) có tổng chia hết cho \(3\).

Example

7
3 6 8 5 3 5 7

6

5
5 6 8 4 3

3

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 < n \le 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): \(10^3 < n \le 10^5\).