Bekzhan Kassenov


Задача №1. 

Задача A. Очередь

Ограничение по времени:
1 секунда
Ограничение по памяти:
64 мегабайта

Бекжану рассказали об одной интересной очереди. Это очередь в кассу, в которой работает не особо добросовестный кассир. Кассир в этой очереди обслуживает клиента, только когда клиент ругается с ним. Время от времени кто-то из очереди осознает, что он опаздывает на очень важную встречу, проходит вне очереди, ругается с кассиром, после чего кассир его обслуживает. Допустим, что человека, прошедшего вне очереди зовут Ануар. Каждый человек, стоявший перед Ануаром в очереди, выразит свое недовольство его поступком в виде какого-то количества слов (фиксированного для каждого говорящего). Наблюдавшему за очередью Бекжану стало интересно, сколько же нелестных слов в свой адрес услышит каждый, прошедший вне очереди?
Формат входного файла
Первая строка входных данных содержит целое число $N$ ($2 \leq N \leq 5 \cdot 10^5$) — число событий в очереди. Описание каждого из событий начинается с целого числа $type$ ($1 \leq type \leq 2$). Если $type = 1$, то за ним следует целое число $w$ ($1 \leq w \leq 10^9$). Данный тип запросов означает, что новый человек пришел в очередь. Его номером является наименьшее целое положительное число, не использованное до этого в качестве номера, а количеством слов, которые он будет произносить при каждом недовольстве — число $w$. Если $type = 2$, то за ним следует целое число $x$. Данный тип запросов означает, что человек с номером $x$ проходит вне очереди. Гарантируется, что в момент запроса человек с таким идентификатором присутствует в очереди. Гарантируется, что хотя бы один человек покинет очередь.
Формат выходного файла
Для каждого прошедшего вне очереди человека выведите, сколько слов возмущения он услышит из очереди.
Система оценки
  1. $N \le 20$, $w \le 1000$. Стоимость подгруппы: $10$ баллов.
  2. $N \le 10000$. Стоимость подгруппы: $40$ баллов.
  3. $N \le 500000$. Стоимость подгруппы: $50$ баллов.
Примеры:
Вход 
2
1 1
2 1
Ответ
0
Вход 
8
1 8
1 1
1 9
2 2
1 2
1 4
2 5
1 3
Ответ
8
19
Замечание
В первом примере человек пришел в очередь, поругался с кассиром и не выслушивал слов ни от кого. Во втором примере в очередь сначала придут люди, которые скажут $8$, $1$ и $9$ слов недовольства соответственно (и получат номера $1$, $2$ и $3$ соответственно). Затем человек с номером $2$ пройдет вне очереди и выслушает недовольство от человека с номером $1$ ($8$ слов). После этого в очередь придут люди с количествами слов $2$ и $4$, и номерами $4$ и $5$ соответственно. Затем человек с номером $5$ пройдет вне очереди и выслушает недовольство от людей с номерами $1$, $3$, $4$ ($19$ слов). Последним в очередь придет человек с номером $6$ и количеством слов $3$ ( Bekzhan Kassenov )
комментарий/решение(1) олимпиада