Задача Figures. Дано набiр з n цифр вiд 0 до 9 включно. Потрібно дiзнатися, яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їх порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язані використати всi цифри.
Математична підказка:
-
Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.
-
Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.
Технічні умови. Програма Figures читає з пристрою стандартного введення у першому рядку одне цiле число n (1 ⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне цiле число — максимальну кiлькiсть чисел кратних 3, що можна скласти з цього набору.
Приклади
| Введення | Виведення |
| 1 0 |
1 |
| 14 8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8 |
Зауваження до прикладів
У першому прикладi ми можемо скласти лише одне число 0.
У другому прикладi з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способiв — це скласти наступнi числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.