题目描述

给定 $n$ 个正整数。每次可以选择两个尚未被选择的数，如果它们的和是 $3$ 的倍数，就可以将这两个数配成一对。

每个数最多属于一对。请计算最多可以配成多少对。

输入格式

第一行包含一个整数 $n$，表示整数的个数。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最多可以配成的对数。

8
1 3 8 4 2 6 7 9

3

数据范围与提示

• $1 \le n \le 100000$
• $1 \le a_i \le 1000000$