ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > 104. Стеки > задача:


Ломбард

Задачи раздела

• Ближайший больший справа
• Ломбард
• Постфиксное выражение
• Скобочная последовательность

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 5000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Ломбард
Ломбард
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Петрович часто пользуется услугами ломбарда. Вот и сегодня он понёс туда тёщины часы.

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

Петрович пытается вести хоть какой-то учёт отданных вещей, поэтому он попросил вас написать для него программу-помощника.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 106) — количество запросов.

Следующие N строк описывают запросы:

  • Запрос «1 X» означает, что Петрович отдаёт в ломбард вещь стоимостью X (1 ≤ X ≤ 1000, стоимости всех вещей целочисленны);
  • Запрос «2» означает, что Петрович выкупает вещь, которую заложил последней. При этом гарантируется, что в ломбарде есть хотя бы одна вещь Петровича;
  • Запрос «3» означает, что Петрович хочет узнать суммарную стоимость всех сданных им в ломбард предметов;
  • Запрос «4» означает, что Петрович хочет узнать стоимость самой дорогой из вещей, сданных им в ломбард. Если таких вещей несколько, рассматривается стоимость любой из них;
  • Запрос «5» означает, что Петрович хочет узнать количество предметов, которые нужно выкупить, чтобы вернуть самую дорогую из вещей в ломбарде. Если таких вещей несколько, рассматривается ближайшая из них (та, возврат которой потребует наименьшего числа выкупов).

Например, если Петрович сдал канделябр за 100 рублей, потом часы за 200 рублей, а затем портсигар за 50 рублей, то:

  • Суммарная стоимость заложенных вещей равна 350 рублей;
  • Наиболее дорогая заложенная вещь (часы) имеет стоимость 200 рублей;
  • Чтобы вернуть самую дорогую вещь, нужно выкупить 2 предмета (портсигар и часы).

Выходные данные

Для каждого из запросов «3», «4» или «5» выведите в отдельной строке одно целое число — соответствующий ответ. Если в некоторый момент времени в ломбарде нет вещей Петровича, то ответом на любой из запросов является число 0.

Примеры

Входные данные
5
1 10
1 5
3
4
5
Выходные данные
15
10
2
Входные данные
11
1 100
3
4
5
1 200
3
4
5
2
2
3
Выходные данные
100
100
1
300
200
1
0

Для отправки решений необходимо выполнить вход.

www.contester.ru