**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**
\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность
\(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за
минуту ( \(0 \leq a_i \leq 10^8\)).
Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке.
От него требуется отцеплять их по одной, отправляя прочь
для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после
всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух
минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только
одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества
молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты
и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова
(скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой
максимально возможное количество молока, которое может собрать фермер Джон, если он
отцепляет своих коров в оптимальном порядке.
Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока
в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\))
каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет
новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что
каждый запрос рассматривает временное потенциальное изменение независимо от всех других
запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.
ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):
Первая строка содержит
\(N\).
Вторая строка содержит \(a_1\dots a_N\).
Третья строка содержит \(Q\).
Следующие \(Q\) строк содержат по два целых числа \(i\) и \(j\), разделенных пробелом.
ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):
Пожалуйста, выведите значение \(T\) для каждого из запросов \(Q\) в отдельных строках.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 10 4 2 6
3
2 1
2 8
4 5
|
55
81
98
|