Монокарп собирает армию в компьютерной игре, чтобы сразиться с драконом.
Армия состоит из двух частей: героев и защитных артефактов. У каждого героя один параметр — его здоровье. У каждого защитного артефакта тоже один параметр — его прочность.
Перед началом боя Монокарп раздает артефакты героям так, чтобы каждый герой получил не более одного артефакта.
Бой состоит из раундов, которые проходят следующим образом:
Бой заканчивается, если в живых не осталось ни одного героя.
Изначально армия пуста. Приходит $$$q$$$ запросов: добавить в армию героя со здоровьем $$$x$$$ или артефакт с прочностью $$$y$$$. После каждого запроса найдите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.
В первой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.
В $$$i$$$-й из следующих $$$q$$$ строк записаны два целых числа $$$t_i$$$ и $$$v_i$$$ ($$$t_i \in \{1, 2\}$$$; $$$1 \le v_i \le 10^9$$$) — тип запроса и величина параметра запроса. Если тип $$$1$$$, то добавляется один герой со здоровьем $$$v_i$$$. Если тип $$$2$$$, то добавляется артефакт с прочностью $$$v_i$$$.
Выведите $$$q$$$ целых чисел. После каждого запроса выведите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.
32 51 41 10
0 8 19
101 91 62 41 81 32 101 31 61 102 6
9 15 19 27 30 39 42 48 59 65
Рассмотрим первый пример.
Название |
---|