T425162 「YAC Round 4」灵梦的香火钱

 > 梦想天生

灵梦今天赛钱箱里面意外多了很多香火钱，大概是因为新年到了哈哈。 在赛钱箱中一共有 $n$ 个钱币，每个钱币对应一个价值 $a_i$。 灵梦需要整理一下这些香火钱，她希望这些钱币两两配对（这里的 **两两配对指的是数字首尾相连**），每个钱币只能用一次。也就是说灵梦配对最多会得到 $\left \lfloor \frac{n}{2} \right \rfloor$ 对钱币，**每一对钱币** 形成的 **价值是两个钱币价值首尾相连得到的数字**。 例如，有两个钱币的价值分别为 $12$ 和 $3$，那么进行配对后这对钱币的价值为 $123$ （或 $312$）。 灵梦想要配对后得到的多对钱币中价值为 $3$ 的倍数的对数 **尽可能多** （未配对的钱币不算）。 请你帮可爱的灵梦计算一下，这 $n$ 个钱币配对后 **最多会有多少 $3$ 的倍数**。

第一行输入一个整数 $n$，表示钱币的个数。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个钱币的价值。

输出一行一个整数，表示配对后最多得到的 $3$ 的倍数。

#### 样例解释 样例1：12 和 3 配对得到 123，11 和 4 配对得到 114，剩余一个 9 没有配对。故答案为 2 。（此样例配对方式不唯一） 样例2：12 和 3 配对得到 123，其余都无法进行配对得到 3 的倍数。故答案为 1 。 #### 数据范围 对于 $20 \%$ 的数据，$1 \le n \le 10$ ; 对于 $40 \%$ 的数据，$1 \le n \le 1000$ ; 对于 $100 \%$ 的数据，$1 \le n \le 10^6$ ，$1 \le a_i \le 10^9$。