Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

C. Счастливые билеты
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Вася считает, что счастливые билеты — это билеты, номера которых делятся на 3 без остатка. Ему удалось собрать достаточно большую коллекцию таких билетов, но однажды его младший брат Леонид обиделся на него и решил уничтожить всю коллекцию. Сначала он разорвал каждый билет ровно на два кусочка, но этого ему показалось мало, поэтому Леонид еще и выкинул часть кусочков. Увидев это, Вася пришел в ужас, но все-таки попытался восстановить коллекцию. Он выбрал несколько пар кусочков, и попарно склеил их так, чтобы каждая пара образовывала счастливый билет. Оставшиеся кусочки Вася, скрепя сердце, выкинул. Таким образом, после склейки 2t кусочков у него получилось t билетов, каждый из которых — счастливый.

Когда Леонид разрывал билет на два кусочка, на одном оказывались первые несколько цифр его номера, а на втором — вся оставшаяся часть.

Каждую пару кусочков Вася может склеить так, как ему захочется, лишь бы получался счастливый билет. Например, кусочки 123 и 99 можно склеить ровно двумя способами: 12399 и 99123.

Какое наибольшее число билетов могло получиться у Вася после этого?

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 104) — количество кусочков. Во второй строке через пробел записано n целых чисел ai (1 ≤ ai ≤ 108) — номера на кусочках. Вася может склеивать кусочки только по два. Даже если номер некоторого кусочка в отдельности является счастливым, Вася должен его склеить этот кусочек с каким-то другим, чтобы он засчитался за счастливый билет. Вася не обязан использовать все кусочки. Номера на кусочках и на получившихся билетах могут совпадать.

Выходные данные

Выведите одно число — какое максимальное количество счастливых билетов удастся восстановить. Не забудьте, что каждый счастливый билет представляет собой ровно два склеенных кусочка.

Примеры
Входные данные
3
123 123 99
Выходные данные
1
Входные данные
6
1 1 1 23 10 3
Выходные данные
1