Cho dãy \(a\) gồm \(N\) số nguyên dương. Hãy cho biết 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 xem có bao nhiêu cặp chỉ số \(i,j(1 \leq i, j \leq N\) so cho tổng \(a_i + a_j\) chia hết cho 3

Input

• Dòng thứ nhất: ghi số nguyên \(N\) \((2 \leq N \leq 10^5)\)
• Dòng thứ 2: Ghi \(N\) số nguyên dương \(a_1, a_2,a_3,...,a_n (1 \leq a_i \leq 10^5, \forall i = 1 -> N)\) là các phần tử của dãy

Output

• Một dòng duy nhất ghi số lượng cặp số của dãy \(a\) có tổng chia hết chho 3

Example

Subtask:

• Subtask 1: \((50% số test)\) \(n \leq 100\)
• Subtask 2: \((50% số test)\) không có ràng buộc gì thêm