Задача Toys2019. У класі НУШ встановили автомат, який продає іграшки (реформа освіти!). Учні, звичайно ж, вишикувались у чергу, але з’ясувалося, що:
- Вартість іграшки – 1 гривня;
- Кожен учень може придбати лише одну іграшку;
- Автомат приймає лише купюри 1, 2 та 5 гривень і видає за потребою решту;
- У кожного учня є лише одна купюра;
- Якщо автомат не має чим видати решту, він зупиняється;
- На початку роботи в автоматі немає жодної купюри;
- Учні категорично не хочуть мінятися місцями в черзі і пропускати інших учнів.
Скільки учнів зможуть придбати іграшки?
Технічні умови. Програма Toys2019 читає з пристрою стандартного введення в першому рядку кількість учнів N – натуральне число, не більше 105, в другому – N розділених пропуском чисел 1, 2 або 5 – номінали купюр учнів в черзі, починаючи від автомата. Програма виводить на пристрій стандартного виведення єдине число – максимальну кількість учнів, що придбають іграшки.
Приклад
Введення
7
1 2 1 2 5 5 1
Виведення
5