题目描述

“三倍游戏”是一种单人小游戏。 玩家会得到 $n$ 个整数 $a_1,a_2,\dots,a_n$。 每一次，玩家可以从这些整数中挑出 两个数字相加：

• 若它们的和是 $3$ 的倍数，就可以把这两个数字 消除。
• 重复上述过程，直到再也无法消除为止。

问：玩家 最多 能消除多少对数字？

输入格式

• 第一行：单个整数 $n$。
• 第二行：$n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一个整数，表示答案。

4
1 3 3 2

2

6
1 1 1 1 1 1

0

数据范围

• $1 \le a_i \le 1\,000\,000$；
• 对于 $50\%$ 的数据，$1 \le n \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n \le 100\,000$。