407260: GYM102739 B Наруто

B. Нарутоограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Никита учится на третьем курсе университета и очень любит смотреть аниме. А сейчас как раз сентябрь — самое время для Наруто. Никита уже настроился посмотреть пару десятков серий, как вдруг ему начали приходить электронные письма с домашками. Каждое письмо содержит собственно домашнее задание и дедлайн — 23:59 одного из последующих дней. Все домашки Никита делает непосредственно в день дедлайна, и выполнение заданий занимает весь день, независимо от их количества (если, например, в какой-то день дедлайн у пяти домашек, Никита сделает их все за этот день, просто не очень старательно).

Изначально Никита планировал посмотреть аниме завтра (в день с номером 1), но каждое приходящее письмо могло изменить его план (например, если пришло письмо с дедлайном в 23:59 первого дня, и такое бывает). После прочтения каждого письма, Никита вносит новое дз в своё расписание, а также корректирует план по просмотру аниме (если нужно).

Помогите Никите автоматизировать этот процесс: после каждого полученного письма выведите ближайший день, свободный от домашек, в который Никита сможет посмотреть Наруто.

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

В первой строке дано одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — число писем, полученных Никитой.

В следующей строке дано $$$q$$$ целых чисел $$$d_i$$$ ($$$1 \le d_i \le 10^9$$$) — день, на который назначен дедлайн в $$$i$$$-м письме.

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

Выведите $$$q$$$ целых чисел: для каждого $$$i \le q$$$ ближайший день, свободный от домашек, назначенных в первых $$$i$$$ письмах.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 19 & q \le 100, d_i \le 100, \text { Все $d_i$ различны} & \text { подзадача } & \\ \hline 2 & 12 & q \le 100, d_i \le 100 & \text { подзадача } & 1 \\ \hline 3 & 26 & q \le 10^5, d_i \le 100 & \text { подзадача } & 1, 2 \\ \hline 4 & 43 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2, 3 \\ \hline \end{array}$$$$$$

ПримерВходные данные

5
1 3 2 6 4

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

2 2 4 4 5