Республиканская олимпиада по информатике 2017 года за 9 класс | Казахстанские олимпиады

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

Бекжану рассказали об одной интересной очереди. Это очередь в кассу, в которой работает не особо добросовестный кассир. Кассир в этой очереди обслуживает клиента, только когда клиент ругается с ним.

Время от времени кто-то из очереди осознает, что он опаздывает на очень важную встречу, проходит вне очереди, ругается с кассиром, после чего кассир его обслуживает.

Допустим, что человека, прошедшего вне очереди зовут Ануар. Каждый человек, стоявший перед Ануаром в очереди, выразит свое недовольство его поступком в виде какого-то количества слов (фиксированного для каждого говорящего).

Наблюдавшему за очередью Бекжану стало интересно, сколько же нелестных слов в свой адрес услышит каждый, прошедший вне очереди?

Формат входного файла

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

Гарантируется, что хотя бы один человек покинет очередь.

Формат выходного файла

Для каждого прошедшего вне очереди человека выведите, сколько слов возмущения он услышит из очереди.

Примеры

Вход

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