当前没有测试数据。

题目描述

数学王国最近流行一种新的消消乐游戏，这个游戏与三有关。

在一个数列中，任意选择两个数碰一下，如果它们的和是三的倍数，这两个数就会消失，反复操作，直到无法再消失为止。

请问最多可以让多少对数消失。

输入格式

读入一个整数 $n$，表示数列中数的个数。

第二行读入 $n$ 个整数。

输出格式

输出一个整数，表示最多可以让多少对数消失。

样例

输入

3
1 3 2

输出

1

输入

8
1 3 8 4 2 6 7 9

输出

3

输入

5
3 6 9 12 15

输出

2

数据范围

对于 $50\%$ 的数据，$1 \le n \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le 100,000$。读入的数列中每个数的范围在 $[1, 1000000]$ 的范围内。