← 返回题目列表

Codeforces · 43/C

C. 幸运券

中文机器翻译题面 查看原题

Vasya认为幸运彩票是那些数字能被3整除的彩票。他收集了相当多的此类彩票,但有一天,他的弟弟Leonid生闷气,决定毁掉这些收藏。首先,他把每张票都撕成两半,但他认为这还不够,列昂尼德也扔掉了一部分。看到这一幕,瓦夏感到害怕,但仍然试图恢复这些藏品。他选择了几对,并将每对粘在一起,这样每对就形成了一张幸运票。剩下的碎片瓦夏不情愿地扔掉了。因此,在粘合 2t 块之后,他最终得到了 t 张门票,每一张都是幸运的。

当列昂尼德将门票撕成两块时,其中一张包含了他的号码的前几个字母,第二张包含了其余的字母。

Vasya 可以用他喜欢的任何方式粘合每一对碎片,但重要的是他最终会得到一张幸运票。例如,第 123 块和第 99 块可以通过两种方式粘合:12399 和 99123。

之后 Vasya 最多可以获得多少张门票?

输入

第一行包含整数 n (1 ≤ n ≤ 104) — 件数。第二行包含 n 个空格分隔的数字 ai (1 ≤ ai ≤ 108) — 棋子上的数字。瓦夏只能将碎片成对粘合。即使一件作品的编号已经是幸运的,瓦夏也应该将这件作品与其他作品粘在一起,这样才算幸运。瓦西亚不必使用所有的碎片。所得门票上的碎片和号码可能会重合。

输出

打印单个数字——能够恢复的幸运券的最大数量。不要忘记,每张幸运券都是由两块粘合在一起的。

示例

输入 #1

3
123 123 99

输出 #1

1

输入 #2

6
1 1 1 23 10 3

输出 #2

1