Trong trung tâm nghiên cứu năng lượng số học, mỗi tinh thể được gán một mức năng lượng là số nguyên dương ~a_i~.

Hai tinh thể được xem là cộng hưởng hoàn hảo nếu tổng năng lượng của chúng chia hết cho 3.

Nhiệm vụ của bạn là đếm số lượng cặp tinh thể thỏa mãn điều kiện trên.

Cụ thể, hãy đếm số cặp chỉ số ~(i, j)~ sao cho:

• ~1 ≤ i < j ≤ n~
• ~a_i + a_j~ chia hết cho ~3~.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương n — số lượng tinh thể (~1 < n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^6, 1 \le i \le n~).

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng cặp ~(i, j)~ thỏa mãn yêu cầu.

Ví dụ

Input

5
1 2 3 4 5

Output

4

Ràng buộc

• Subtask 1 (60% số điểm): ~n \le 10^3~

• Subtask 2 (40% số điểm): ~n \le 10^6~