Cho dãy gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3.
Nói cách khác, bạn phải đếm số lượng cặp chỉ số i, j (1 ≤ i < j ≤ n) sao cho a[i] + a[j] chia hết cho 3.

Input

Dữ liệu vào:

• Dòng 1: Một số nguyên duy nhất n (1 ≤ n ≤ 10⁵).
• Dòng 2: Gồm n số nguyên dương a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 10⁵).

Output

In ra một số nguyên duy nhất là số lượng cặp (i, j) sao cho a[i] + a[j] chia hết cho 3.

Ví dụ

Input:
5
3 4 2 3 4

Output:
3

Input:
4
3 6 9 12


Output:
6

Giải thích

Ví dụ 1: Có 3 cặp thoả mãn: (1,4), (2,3), (3,5)

Ví dụ 2: Có 6 cặp thoả mãn: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)