A. 【J】T1小清新清新题

给你一个长为 n 的数组 a_1,a_2,\cdots,a_n。

对于每一次操作，你可以选择数组中两个位置不同的元素，然后把它们删除，并将它们的和放在数组的末尾。

比如说，如果 a={1,1,2}，那么你可以通过一次操作得到 {2,2} 或者 {1,3}。

你可以进行任意次操作，使得这个数组中能够被 3 整除的数最多。你需要输出这个数量。

第一行输入一个正整数 n，表示数组的长度。

第二行输入一个长为 n 的数组 a_1,a_2,\cdots,a_n。

输出一行，表示你的答案。

数据范围

对于 10\% 的数据，1\leq n\leq 5；

对于 30\% 的数据，1\leq n\leq 50；

对于另外 5\% 的数据，所有的 a_i 都为 3 的倍数；

对于另外 10\% 的数据，所有的 a_i 除以 3 的余数都为 1；

对于另外 10\% 的数据，1\leq a_i\leq 3；

对于全部数据，1\leq n\leq 10^5，1\leq a_i\leq 10^9。

样例解释

对于第一个样例，进行如下操作：{3,\underline{1},\underline{2},2,1}\to{3,\underline{2},\underline{1},3}\to{3,3,3}，即可得到 3 个能被 3 整除的数。

对于第二个样例，进行如下操作：{1,1,4,\underline{5},1,\underline{4}}\to{1,1,\underline{4},\underline{1},9}\to{1,\underline{1},9,\underline{5}}\to{1,9,6}，此时答案为 2。

可以证明，以上均为最优解。