Statement is not available in English language
D. Высадка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На планете Арракис вокруг пустыни расположены $$$N$$$ поселений. В $$$i$$$-м поселении может разместиться $$$P_i$$$ колонистов. Челнок, доставляя новых колонистов с орбиты, делает $$$M$$$ рейсов. $$$j$$$-й рейс приземляется возле поселения $$$X_j$$$ и привозит $$$K_j$$$ колонистов.

Часть колонистов остается в поселении $$$X_j$$$. Те, для кого места в этом поселении нет, движутся вокруг пустыни наземным транспортом в следующие поселения, в порядке увеличения номера поселения. После $$$N$$$-го поселения следующим является поселение с номером $$$1$$$. Если в следующем поселении есть места, то часть колонистов остается там. Остальные продолжают движение.

Для каждого рейса нужно подсчитать расходы на перевозку колонистов наземным транспортом, как сумму расстояний, на которое нужно перевезти каждого колониста. Расстояние между соседними поселениями будем считать равным $$$1$$$. Первоначально все поселения пустые и заполняются по мере выполнения рейсов.

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

Первая строка ввода содержит одно целое число $$$N$$$ $$$(2 \le N \le 100000)$$$ – количество поселений.

Вторая строка ввода содержит $$$N$$$ целых чисел $$$P_i$$$ $$$(1 \le Pi \le 10^9)$$$ – вместимость поселений.

Третья строка ввода содержит одно целое число $$$M$$$ $$$(1 \le M \le 100000)$$$ – количество рейсов.

Следующие $$$M$$$ строк содержат по два целых числа – номер поселения, возле которого приземляется челнок $$$X_j$$$ $$$(1 \le X_j \le N)$$$ и количество колонистов в челноке $$$K_j$$$ $$$(1 \le K_j \le 10^9)$$$. Гарантируется, что сумма всех $$$K_j$$$ не превышает суммы всех $$$P_i$$$.

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

Для каждого рейса вывести на отдельной строке расходы на перевозку колонистов наземным транспортом.

Система оценки

Подзадача 1 (40 баллов) $$$1 \le N \le 100, 1 \le M \le 100, 1 \le P_i \le 100, 1 \le K_j \le 100$$$ В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 2 (30 баллов) $$$100 \lt N \le 1000, 100 \lt M \le 1000, 1 \le P_i \le 10^9, 1 \le K_j \le 10^9$$$ Необходимые подзадачи: 1. В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 3 (30 баллов) $$$1000 \lt N \le 100000, 1000 \lt M \le 100000, 1 \le P_i \le 10^9, 1 \le K_j \le 10^9$$$ Необходимые подзадачи: 1, 2. В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Пример
Входные данные
5
3 3 4 5 1
2
2 11
3 3
Выходные данные
12
6
Примечание

Пояснение к примеру: Из 11 прибывших 1-м рейсом колонистов 3 остаются в поселении №2, 4 остаются в поселении №3, 4 – в поселении №4. Расходы на перевозку равны 3 $$$0+4 1+4 2=12$$$. После размещения колонистов в поселениях остается следующее количество свободных мест: $$$(3,0,0,1,1)$$$. Из 3 прибывших 1-м рейсом колонистов 1 остается в поселении №4, 1 - в поселении №5, еще 1, проехав поселение №5, доезжает до поселения №1. Расходы на перевозку равны $$$1⋅1+1⋅2+1⋅3=6$$$.