Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

G. Серверы

Задачу добавил: alef

Успешно сдано решений: 7

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

Поскольку нагрузка на онлайн-платформу при запуске новых курсов будет возрастать, министерство науки планирует арендовать дополнительные серверы. Всего для аренды доступно $$$n$$$ серверов, и для каждого из них известна стоимость аренды в настоящий момент: аренда сервера $$$\#j$$$ стоит $$$s_j$$$.

Когда владельцы серверов из заслуживающих доверия источников узнают, что в министерстве науки обсуждается запуск новых курсов, они поднимают арендную плату. Между владельцами серверов существует договорённость, что арендная плата за любой сервер увеличивается на одну и ту же величину.

Впрочем, министерство науки добилось царского указа, согласно которому стоимость аренды одного сервера не должна быть больше $$$n$$$. И если после увеличения арендной платы стоимость аренды сервера $$$\#j$$$ стала равной $$$\widetilde{s_j}$$$ и оказалась больше значения $$$n$$$, то стоимость аренды сервера считается равной $$$\widetilde{s_j} - n$$$. Конечно, это не нравится владельцам, но пока они не достигли новой договорённости, они соблюдают имеющуюся.

В вашем распоряжении имеется список событий двух типов:

  • владельцы серверов узнают об очередном обсуждении в министерстве и поднимают арендную плату за серверы;

  • министерство науки планирует арендовать $$$m$$$ серверов и интересуется, какая минимальная сумма на это потребуется.

События происходят последовательно, в порядке их упоминания в списке. Ваша задача  — дать ответы на запросы министерства.

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

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

В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — количество серверов, доступных для аренды.

Во второй строке содержатся $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \le s_j \le n, \, j =1, 2, \ldots, n)$$$ — начальные арендные стоимости серверов.

В третьей строке содержится целое число $$$q$$$ $$$(1 \le q \le 5 \cdot 10^5)$$$ — количество событий в списке.

В каждой из следующих $$$q$$$ строк содержится описание одного из событий. Описание состоит из двух целых чисел $$$t_k$$$ и $$$z_k$$$ $$$(t_k \in \{1, 2\}, \, 1 \le z_k \le n, \, k = 1, 2, \ldots, q)$$$, разделённых пробелом.

Если $$$t_k = 1$$$, то $$$z_k$$$ — это величина, на которую владельцы серверов увеличивают арендную плату.

Если же $$$t_k = 2$$$, то $$$z_k$$$ — это количество серверов, которое планирует арендовать министерство.

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

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

Разделяйте ответы переводами строк или пробелами.

Пример

Входные данные
4
1 1 2 3
10
2 1
1 3
2 1
2 2
1 1
2 1
1 2
2 1
2 2
2 4
Выходные данные
1
1
3
1
1
4
11

Сдать задачу

Задать вопрос жюри по этой задаче