Задача №114713. Фэйк Ньюз
В Байтландии зарегистрировано несколько информационных агенств, в том числе новое информационное агенство ООО «неверлай дот ком». Начальник этой организации хочет выпустить сенсационное расследование. Последний месяц он ждет подходящего момента, чтобы новость стала как можно более популярной.
У каждого агенства есть свой показатель авторитетности \(A\), который может отличаться для разных агенств. Процесс публикации новости в Байтландии устроен так: первым делом агенство ООО «неверлай дот ком» публикует новость. Это запускает цепную реакцию, устроенную следующим образом:
- Каждое агенство из тех, кто еще не опубликовал данную новость, вычисляет число \(P\): количество других агенств, опубликовавших новость.
- Если агенство имеет показатель авторитетности \(A\), а число уже опубликовавших новость агенств \(P\) не меньше \(A\), то это агенство публикует данную новость.
- Процесс повторяется до тех пор, пока предыдущее условие выполняется хотя бы для одного из агенств.
ООО «неверлай дот ком» хочет выбрать момент, когда им стоит опубликовать новость, но в Байтландии часто появляются новые информационные агенства, а старые часто закрываются. От вас требуется обрабатывать запросы двух типов:
- \(+\ A\) появляется новое агенство с показателем авторитетности \(A\).
- \(-\ A\) одно из агенств с показателем авторитетности \(A\) прекращает работу.
Для запросов второго типа гарантируется, что существовало хотя бы одно СМИ с показателем авторитетности \(A\). Обратите внимание, что в один момент может существовать несколько агенств с одинаковым показателем авторитетности \(A\).
После каждого запроса вам требуется определить, сколько агенств опубликуют новость, если ООО «неверлай дот ком» опубликует ее прямо сейчас.
В первой строке задано целое число \(n\) (\(1 \le n \le 500\,000\)) — количество запросов.
В следующих \(n\) строках вводятся запросы в формате, описанном в условии задачи: сначала задаётся один из символов {« + », « - »}, затем следует целое число \(A\) — показатель авторитетности (\(1 \le A \le 500\,000\)).
Выведите \(n\) строк. В каждой строке должно быть одно число — количество агенств, которые опубликуют новость от ООО «неверлай дот ком» после \(i\)-го запроса.
Рассмотрим первый пример:
- После первого запроса ни одно другое агенство не будет публиковать новость от ООО «неверлай дот ком».
- После второго запроса появилось агенство, которое готово опубликовать новость.
- После третьего запроса все еще лишь одно агенство готово опубликовать новость.
-
После четвёртого запроса процесс публикации будет устроен следующим образом:
- ООО «неверлай дот ком» публикует новость.
- агенство с \(A = 1\) публикует новость.
- агенство с \(A = 2\) публикует новость.
- агенство с \(A = 3\) публикует новость.
- агенство с \(A = 4\) публикует новость.
- После последнего запроса процесс публикации остановится на агенстве с \(A=2\).
5 + 4 + 1 + 3 + 2 - 3
1 2 2 5 3
8 + 1 + 1 + 2 - 1 + 4 - 1 + 1 + 1
2 3 4 3 3 1 3 5