G. Переменный урон
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп собирает армию в компьютерной игре, чтобы сразиться с драконом.

Армия состоит из двух частей: героев и защитных артефактов. У каждого героя один параметр — его здоровье. У каждого защитного артефакта тоже один параметр — его прочность.

Перед началом боя Монокарп раздает артефакты героям так, чтобы каждый герой получил не более одного артефакта.

Бой состоит из раундов, которые проходят следующим образом:

  • сначала дракон наносит каждому герою урон, равный $$$\frac{1}{a + b}$$$ (вещественное число без округления), где $$$a$$$ — количество живых героев, а $$$b$$$ — количество активных артефактов;
  • после этого все герои со здоровьем $$$0$$$ или меньше умирают;
  • наконец, некоторые артефакты деактивируются. Артефакт с прочностью $$$x$$$ деактивируется, когда происходит одно из следующего: герой, держащий артефакт, либо умирает, либо получает суммарно $$$x$$$ урона (от начала боя). Если артефакт не выдан ни одному из героев, он считается неактивным с самого начала битвы.

Бой заканчивается, если в живых не осталось ни одного героя.

Изначально армия пуста. Приходит $$$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$$$ целых чисел. После каждого запроса выведите максимальное количество раундов, которые Монокарп может продержаться, если оптимально распределит артефакты.

Примеры
Входные данные
3
2 5
1 4
1 10
Выходные данные
0
8
19
Входные данные
10
1 9
1 6
2 4
1 8
1 3
2 10
1 3
1 6
1 10
2 6
Выходные данные
9
15
19
27
30
39
42
48
59
65
Примечание

Рассмотрим первый пример.

  • Добавляется артефакт с прочностью $$$5$$$. Так как героев пока нет, бой сразу же заканчивается.
  • Добавляется герой со здоровьем $$$4$$$. Монокарп может дать ему артефакт с прочностью $$$5$$$. Сначала идут раунды, в которых герою наносится $$$\frac{1}{1 + 1} = \frac{1}{2}$$$ урона. Через $$$8$$$ таких раундов суммарно будет нанесено $$$4$$$ урона, и герой умрет, а артефакт деактивируется. Больше в живых нет героев, так что бой заканчивается за $$$8$$$ раундов.
  • Добавляется герой со здоровьем $$$10$$$. Пусть теперь артефакт с прочностью $$$5$$$ будет у этого героя. Тогда за первые $$$12$$$ раундов героям будет нанесено $$$12 \cdot \frac{1}{2 + 1} = 4$$$ урона, и первый герой умрет. У второго героя осталось $$$6$$$ здоровья, а у артефакта $$$1$$$ прочности. Теперь урон равен $$$\frac{1}{2}$$$, поэтому еще за $$$2$$$ раунда артефакт деактивируется. У второго героя осталось $$$5$$$ здоровья. За еще $$$5$$$ раундов умрет второй герой. Поэтому ответ равен $$$12 + 2 + 5 = 19$$$.