Chia hết cho 3

Cho dãy ~A=\{a_1, a_2, \ldots, a_n\}~ là các số nguyên dương. Hãy đếm xem có bao nhiêu cặp số trong dãy chia hết cho 3. Nói cách khác đếm xen có bao nhiêu cặp ~(a_i, a_j), 1 \le i < j \le n~ sao cho ~a_i+a_j~ chia hết cho 3.

Input

Dòng 1 chứa số nguyên ~n~ thỏa ~1 \le n \le 10^5~.

Dòng 2 chứa dãy số ~a_1, a_2, \ldots, a_n~ thỏa ~1 \le a_i \le 10^5~.

Output

In ra kết quả cần đếm.

5
3 4 2 3 4

3

4
3 6 9 12

6