G. Серверы
Задачу добавил: alef
Успешно сдано решений: 8
Поскольку нагрузка на онлайн-платформу при запуске новых курсов будет возрастать, министерство науки планирует арендовать дополнительные серверы. Всего для аренды доступно $$$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