题目描述

翁老师会得到 $n$ 个整数 $a_1,a_2,…,a_n$。翁老师可以从这些整数中不断挑出两个数字相加，如果它们的和是 $3$ 的倍数，则这两个整数就被消除，直到不能再消除数字为止。

请问翁老师最多能消除多少对数字？

输入格式

输入包括两行。

第一行包含一个整数 $n$ ，为整数的数量。

第二行包含$n$个整数$a_1,a_2,…,a_n$。

输出格式

输出包括一行，为翁老师最多能消除数字的对数。

4
1 3 3 2

2

6
1 2 3 4 5 6

3

提示

样例 1 解释

可以挑选$(1, 2)$和$(3, 3)$两对数字。

样例 2 解释

可以挑选$(1, 2),(3, 6),(4,5)$共三对数字。

数据范围

对于 $100\%$ 的数据满足，$1\leq n\leq 10^5$，$1\leq a_i\leq 10^9$。

• 子任务 1（30 分）：$1 \le n \le {10}^5$，$1\leq a_i\leq 3$。
• 子任务 2（20 分）：$1 \le n \le {10}^3$，$1 \le a_i \le {10}^9$。
• 子任务 3（50 分）：没有特殊限制。