409855: GYM103810 D Высадка

На планете Арракис вокруг пустыни расположены $$$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<N \le 1000, 100 < M \le 1000, 1 \le P_i \le 10^9, 1 \le K_j \le 10^9$$$ Необходимые подзадачи: 1. В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 3 (30 баллов) $$$1000 < N \le 100000, 1000<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$$$.