Gotham city is in danger. All the people from Gotham were airlifted and they are going to be dropped at different districts of a new safe city.

There are $N$ districts located at position $(1, 2, \ldots, N)$ in a straight line in this newly built safe city.
An array(P) is given which tells us about the maximum capacity of people that can be accommodated in the districts.

There is a condition that people can move only in the forward direction(i.e from city $i$ to $i+1$ for $1 ≤ i < N$) to get shelter.
People want to travel as little as possible to get shelter.
The sad part is that in case any person who does not get shelter is going to die.

Initially, all the districts in the new city are empty.

You are asked $Q$ queries.
Each query consists of two Integers $X$ and $K$, where $K$ denotes the number of people who are going to be dropped at district $X$.
You are required to print the total sum of distance traveled by the people in the current query(that got shelter or did not die) in a new line.

Note:- Queries are not independent(they depend on the previous queries).

------ Input ------

First Line consists of one Integer $N$, where $N$ is the number of districts.
Second line consists of $N$ integers of (array P) separated by a space.
Third Line contains an integer $Q$, which denotes the number of queries.
Next, $Q$ lines consist of two integers $X$ and $K$ separated by space.

------ Output ------

For each query, you have to print the total sum of distance traveled by the people in the current query(that got shelter or did not die ) in a new line.

------  Constraints ------

$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$1 ≤ X ≤ N$
$1 ≤ P[i] ≤ 10^{9}$
$1 ≤ K ≤ 10^{9}$

------  Example Input ------

4
5 5 6 1
2
2 11
2 3

------  Example Output ------

6
2

------  Explanation ------

Query $1$: $5$ people will get shelter in city $2$ and the remaining $6$ will get shelter in city $3$. So, the total distance covered in this query is $6$.
Query $2$: Only $1$ person can get shelter in city $4$ and the rest will die. So, the total distance traveled is $2$.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
ls = list(map(int, input().split()))
q = int(input())
red = [0] * n
for x in range(n - 1):
	red[x] = x + 1
red[-1] = -1
for _ in range(q):
	lk = list(map(int, input().split()))
	pos = lk[0]
	peo = lk[1]
	dis = 0
	tmp = pos
	i = pos - 1
	todo = []
	while i < n:
		if peo >= ls[i]:
			dis += ls[i] * (i - pos + 1)
			peo -= ls[i]
			ls[i] = 0
			tmp = red[i]
			todo.append(i)
		else:
			ls[i] -= peo
			dis += peo * (i - pos + 1)
			peo = 0
			tmp = i
		if peo == 0 or red[i] == -1:
			break
		i = red[i]
	for x in todo:
		red[x] = tmp
	print(dis)


def answer(x, k):
	ans = 0
	(i, p) = (x, k)
	while i != n:
		t = p
		p = max(0, p - a[i])
		a[i] -= min(a[i], t)
		if p == 0:
			if a[i] == 0:
				i = nextind[i]
			break
		dist = nextind[i] - i
		ans += dist * p
		i = nextind[i]
	ans = ans - (n - x) * p
	p = 0
	while x < i:
		nextind[x] = max(nextind[x], i)
		x += 1 << p
		p += 1
	return ans
n = int(input())
a = list(map(int, input().split()))
nextind = [i for i in range(1, n + 1)]
for q in range(int(input())):
	(x, k) = map(int, input().split())
	print(answer(x - 1, k))


n = int(input())
p = list(map(int, input().split()))
q = int(input())
nxt = [i + 1 for i in range(n)]
for i in range(q):
	(x, k) = map(int, input().split())
	x = x - 1
	ans = 0
	stck = []
	curr = x
	while k > 0 and curr != n:
		if p[curr] == 0:
			curr = nxt[curr]
		elif p[curr] == k:
			ans += (curr - x) * k
			k = 0
			p[curr] = 0
		elif p[curr] < k:
			ans += (curr - x) * p[curr]
			k -= p[curr]
			p[curr] = 0
			stck.append(curr)
			curr = nxt[curr]
		else:
			ans += (curr - x) * k
			p[curr] -= k
			k = 0
	while stck:
		nxt[stck.pop()] = curr
	print(ans)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(1):
	n = int(input())
	a = get_array()
	q = int(input())
	arr = [i for i in range(n)]
	for i in range(q):
		(ind, k) = get_ints()
		ind -= 1
		x = bisect.bisect_left(arr, ind)
		ans = 0
		while arr and x < len(arr):
			if k == 0:
				break
			z = a[arr[x]]
			if z > k:
				ans += k * (arr[x] - ind)
				a[arr[x]] -= k
				k = 0
				break
			else:
				ans += z * (arr[x] - ind)
				k -= z
				del arr[x]
		print(ans)


import sys, math, itertools, random, bisect
from collections import defaultdict
sys.setrecursionlimit(999999999)
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(1):
	n = int(input())
	a = [0] + get_array()
	q = int(input())
	par = [i for i in range(n + 1)]
	ans = [0]

	def find(ind, val, x):
		if par[x] != x:
			par[x] = find(ind, val, par[x])
		else:
			temp = min(val, a[x])
			ans[0] += temp * (x - ind)
			val -= temp
			a[x] -= temp
			if a[x] == 0:
				if x < n:
					par[x] = par[x + 1]
					if val:
						par[x] = find(ind, val, par[x])
		return par[x]
	for i in range(q):
		ans[0] = 0
		(ind, val) = get_ints()
		find(ind, val, ind)
		print(ans[0])


n = int(input())
arr = list(map(int, input().split()))
dp = [i + 1 for i in range(n)]
q = int(input())
mini = 0
for _ in range(q):
	ans = 0
	(x, k) = map(int, input().split())
	x = x - 1
	nb = x
	i = x
	zero = []
	while i < n:
		if arr[i] <= k:
			ans = ans + (i - x) * arr[i]
			k = k - arr[i]
			arr[i] = 0
			nb = dp[i]
			zero.append(i)
		else:
			ans = ans + k * (i - x)
			arr[i] = arr[i] - k
			nb = i
			k = 0
		if k == 0:
			break
		i = dp[i]
	for idx in zero:
		dp[idx] = nb
	print(ans)


N = int(input())
a = list(map(int, input().split()))
p = [i + 1 for i in range(N)]
for _ in range(int(input())):
	(X, K) = map(int, input().split())
	i = X - 1
	X -= 1
	s = 0
	temp = X
	indexs = []
	while i < N:
		if a[i] <= K:
			s += a[i] * (i - X)
			K -= a[i]
			a[i] = 0
			temp = p[i]
			indexs.append(i)
		else:
			s += K * (i - X)
			a[i] -= K
			K = 0
			temp = i
		if K == 0:
			break
		i = p[i]
	for j in indexs:
		p[j] = temp
	print(s)


n = int(input())
p = list(map(int, input().split()))
q = int(input())
ind = []
for i in range(n):
	ind.append(i + 1)
for _ in range(q):
	(x, k) = map(int, input().split())
	ans = 0
	temp = x
	i = x - 1
	st = []
	while i < n:
		if k >= p[i]:
			ans += (i - x + 1) * p[i]
			k -= p[i]
			p[i] = 0
			temp = ind[i]
			st.append(i)
		else:
			ans += (i - x + 1) * k
			p[i] -= k
			k = 0
			temp = i
		if k == 0:
			break
		i = ind[i]
	for j in st:
		ind[j] = temp
	print(ans)


N = int(input())
space = list(map(int, input().split()))
Q = int(input())
near = -1
while Q:
	Q -= 1
	(X, K) = map(int, input().split())
	X -= 1
	if space[X] >= K:
		space[X] -= K
		print(0)
	elif near == -1 or X < near:
		rest = K - space[X]
		space[X] = 0
		count = 1
		ans = 0
		for k in range(X + 1, len(space)):
			if space[k] > 0:
				ans += count * min(space[k], rest)
				(space[k], rest) = (space[k] - min(space[k], rest), rest - min(space[k], rest))
			if rest == 0:
				break
			count += 1
		if ans == 0 and (near == -1 or X <= near):
			near = X
		print(ans)
	else:
		print(0)


n = int(input())
a = list(map(int, input().split()))
nxt = [i + 1 for i in range(n)]
for _ in range(int(input())):
	(x, k) = map(int, input().split())
	x -= 1
	idx = x
	ans = 0
	while idx < n and k > 0:
		st = []
		r = min(a[idx], k)
		a[idx] -= r
		k -= r
		ans += (idx - x) * r
		while idx < n and a[idx] == 0:
			st.append(idx)
			idx = nxt[idx]
		while st:
			nxt[st.pop()] = idx
	print(ans)


from os import path
import sys, time
from collections import defaultdict, Counter, OrderedDict, deque
maxx = float('inf')
localsys = 0
mod = int(1000000000.0 + 7)
if path.exists('input.txt'):
	localsys = 1
	start_time = time.time()
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
nxt = [i + 1 for i in range(n)]
for _ in range(int(input())):
	(x, k) = map(int, input().split())
	x -= 1
	idx = x
	ans = 0
	while idx < n and k > 0:
		st = []
		r = min(a[idx], k)
		a[idx] -= r
		k -= r
		ans += (idx - x) * r
		while idx < n and a[idx] == 0:
			st.append(idx)
			idx = nxt[idx]
		while st:
			nxt[st.pop()] = idx
	print(ans)
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


n = int(input())
a = list(map(int, input().split()))
q = int(input())
ptr = -1
for i in range(q):
	(start, eng) = map(int, input().split())
	start -= 1
	if a[start] >= eng:
		a[start] -= eng
		print(0)
	elif ptr == -1 or start < ptr:
		ans = 0
		eng -= a[start]
		a[start] = 0
		for j in range(start + 1, n):
			if a[j] <= eng and a[j] > 0:
				ans += (j - start) * a[j]
				eng -= a[j]
				a[j] = 0
			elif a[j] > 0:
				a[j] = a[j] - eng
				ans += (j - start) * eng
				break
			if eng == 0:
				break
		if ans == 0 and (ptr == -1 or start <= ptr):
			ptr = start
		print(ans)
	else:
		print(0)


import sys
from collections import defaultdict

def pr(n):
	sys.stdout.write(str(n))
	sys.stdout.write('\n')

def inp1():
	return int(sys.stdin.readline())

def inp2():
	return list(map(int, sys.stdin.readline().split()))
if 1:
	n = inp1()
	l = inp2()
	q = inp1()
	d = defaultdict(lambda : 0)
	for i in range(n):
		d[i] = i
	le = []
	for i in range(n):
		if l[i] == 0:
			le.append(i)
		else:
			for j in le:
				d[j] = i
			le = []
	for i in le:
		d[i] = n
	for __ in range(q):
		(x, k) = inp2()
		ans = 0
		i = d[x - 1]
		ind = n
		le = [x - 1]
		while i < n:
			if l[i] == 0:
				i = d[i]
				continue
			if l[i] < k:
				ans += l[i] * abs(x - i - 1)
				k -= l[i]
				l[i] = 0
				le.append(i)
			elif l[i] == k:
				ans += k * abs(x - i - 1)
				l[i] = k = 0
				le.append(i)
				ind = i + 1
				break
			else:
				ind = i
				ans += k * abs(x - i - 1)
				l[i] = l[i] - k
				break
			i += 1
		for j in le:
			d[j] = ind
		pr(ans)


from os import path
import sys, time
from math import ceil, floor, gcd, log, log2, factorial
from collections import defaultdict, Counter, OrderedDict, deque
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
localsys = 0
if path.exists('input.txt'):
	localsys = 1
	start_time = time.time()
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
q = int(input())
parent = [i + 1 for i in range(n)]
for i in range(q):
	(x, k) = map(int, input().split())
	x -= 1
	ans = 0
	idx = x
	st = []
	while k > 0 and idx < n:
		if a[idx] == 0:
			idx = parent[idx]
		elif a[idx] == k:
			ans += (idx - x) * k
			k = a[idx] = 0
		elif a[idx] < k:
			ans += (idx - x) * a[idx]
			k -= a[idx]
			a[idx] = 0
			st.append(idx)
			idx = parent[idx]
		else:
			ans += (idx - x) * k
			a[idx] -= k
			k = 0
	while st:
		parent[st.pop()] = idx
	print(ans)
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


n = int(input())
P = list(map(int, input().split()))
d = [i + 1 for i in range(n)]
qer = int(input())
for q in range(qer):
	ans = 0
	(x, k) = map(int, input().split())
	i = x - 1
	while i < n and k != 0:
		sub = min(P[i], k)
		ans += sub * (i - (x - 1))
		P[i] -= sub
		k -= sub
		if i != x - 1:
			d[x - 1] = i
		i = d[i]
	print(ans)


n = int(input())
a = list(map(int, input().split()))
b = [i + 1 for i in range(n)]
q = int(input())
for i in range(q):
	(district, people) = map(int, input().split())
	district -= 1
	i = district
	c = []
	travelled = 0
	while i < n:
		if a[i] == 0:
			i = b[i]
			continue
		val = min(people, a[i])
		people -= val
		a[i] -= val
		travelled += val * (i - district)
		if people == 0:
			break
		c.append(i)
		i = b[i]
	for y in c:
		b[y] = i
	print(travelled)


n = int(input())
l = list(map(int, input().split()))
q = int(input())
s = [0] * n
r = [i + 1 for i in range(n)]
for i in range(q):
	(x, k) = map(int, input().split())
	x -= 1
	j = x
	ans = 0
	stk = []
	while x < n:
		if k <= 0:
			break
		elif s[x] < l[x]:
			if k >= l[x] - s[x]:
				k -= l[x] - s[x]
				ans += (x - j) * (l[x] - s[x])
				s[x] = l[x]
				stk.append(x)
				x = r[x]
			else:
				s[x] += k
				ans += (x - j) * k
				k = 0
		else:
			x = r[x]
	while stk:
		r[stk.pop()] = x
	print(ans)


rr = lambda : input().strip()
rrm = lambda : map(int, rr().split())
N = int(rr())
cap = list(rrm())
Q = int(rr())
nex_ind = [i + 1 for i in range(N)]

def solve():
	(X, K) = rrm()
	trav = 0
	X -= 1
	beg = X
	travel = []
	while X < N:
		delta = min(K, cap[X])
		trav += delta * (X - beg)
		cap[X] -= delta
		K -= delta
		if K == 0:
			break
		travel.append(X)
		X = nex_ind[X]
	for i in travel:
		nex_ind[i] = X
	return trav
for _ in range(Q):
	ans = solve()
	print(ans)


T = int(input())
B = list(map(int, input().strip().split()))
dismap = {}
for b in range(len(B)):
	dismap[b + 1] = b
q = int(input())
for a in range(q):
	tem = list(map(int, input().strip().split()))
	x = tem[0]
	k = tem[1]
	ans = 0
	ind = dismap[x]
	if ind != -1:
		if k <= B[ind]:
			B[ind] -= k
			ans += (ind + 1 - x) * k
			k = 0
		else:
			while k and ind < len(B):
				if k <= B[ind]:
					B[ind] -= k
					ans += k * (ind + 1 - x)
					k = 0
					break
				else:
					k -= B[ind]
					ans += B[ind] * (ind - x + 1)
					B[ind] = 0
					ind = ind + 1
			i = ind
			if i == len(B):
				while x - 1 < i:
					dismap[x] = -1
					x += 1
			else:
				while x - 1 < i:
					dismap[x] = i
					x += 1
	print(ans)


def fun1():
	t = int(input())
	while t > 0:
		t -= 1
		(N, M, K) = map(int, input().split())
		G = list(map(int, input().split()))
		uvd = []
		for j in range(M):
			l = list(map(int, input().split()))
			uvd.append(l)
		binary = []
		for i in range(0, 2 ** N):
			elements = bin(i)[2:]
			binary.append('0' * (N - len(elements)) + elements)
		lst = []
		for elements in binary:
			s1 = 0
			for i in range(N):
				s1 += int(elements[i]) * G[i]
			s2 = 0
			for i in range(M):
				if elements[uvd[i][0] - 1:uvd[i][1]].count('0') > 0:
					continue
				s2 += uvd[i][2]
			lst.append(s2 + s1)
		lst.sort(reverse=True)
		print(*lst[0:K])
n = int(input())
p = list(map(int, input().split()))
query = int(input())
index = [p[i] for i in range(n)]
last = -1
while query:
	query -= 1
	(x, k) = map(int, input().split())
	x -= 1
	if index[x] >= k:
		index[x] -= k
		print(0)
		continue
	elif last == -1 or x < last:
		rest = k - index[x]
		index[x] = 0
		count = 1
		ans = 0
		for k in range(x + 1, len(index)):
			if index[k] > 0:
				ans += count * min(index[k], rest)
				(index[k], rest) = (index[k] - min(index[k], rest), rest - min(index[k], rest))
			if rest == 0:
				break
			count += 1
		if ans == 0 and (last == -1 or x <= last):
			last = x
		print(ans)
	else:
		print(0)


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def solve():
	n = ii()
	arr = [0]
	for x in li():
		arr.append(x)
	pos = [x for x in range(0, n + 1)]
	for p in range(ii()):
		dist = 0
		(x, k) = mi()
		i = pos[x]
		dist = 0
		v = i - x
		while i <= n:
			if arr[i] >= k:
				arr[i] -= k
				dist += k * v
				break
			else:
				k -= arr[i]
				dist += arr[i] * v
				v += 1
				arr[i] = 0
			i += 1
		if i > n + 1:
			i = n + 1
		if i != n + 1 and arr[i] == 0:
			i += 1
		x = pos[x]
		while x <= n and arr[x] == 0:
			pos[x] = i
			x += 1
		print(dist)
for _ in range(1):
	solve()


n = int(input())
a = list(map(int, input().split()))
b = [i + 1 for i in range(n)]
q = int(input())
for _ in range(q):
	(x, y) = map(int, input().split())
	x -= 1
	z = x
	c = []
	d = 0
	while x < n:
		if a[x] == 0:
			x = b[x]
			continue
		delta = min(a[x], y)
		a[x] -= delta
		y -= delta
		d += delta * (x - z)
		if y == 0:
			break
		c.append(x)
		x = b[x]
	for y in c:
		b[y] = x
	print(d)


import math

def solve():
	n = int(input())
	p = list(map(int, input().split()))
	q = int(input())
	y = 0
	cities = {}
	for i in range(q):
		(x, k) = map(int, input().split())
		x -= 1
		y = x
		dist = 0
		ref = [x]
		while k > 0 and x < n:
			if x in cities:
				x = cities[x][0]
				continue
			if k < p[x]:
				p[x] -= k
				dist += (x - y) * k
				k = 0
			elif p[x] > 0:
				k -= p[x]
				dist += (x - y) * p[x]
				p[x] = 0
				cities[x] = ref
				x += 1
			else:
				x += 1
		ref[0] = x
		print(dist)
solve()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = 1
for _ in range(t):
	n = ip()
	arr = list(inp())
	q = ip()
	dp = [i for i in range(n)]
	ans = 0
	for i in range(q):
		(p, val) = inp()
		p -= 1
		ct = dp[p] - p
		p = dp[p]
		ans = 0
		for j in range(p, n):
			if val >= arr[j]:
				val -= arr[j]
				ans += ct * arr[j]
				arr[j] = 0
			else:
				arr[j] -= val
				ans += val * ct
				break
			ct += 1
		if j == n:
			j -= 1
		for jj in range(j, p - 1, -1):
			dp[jj] = j
		print(ans)


from collections import defaultdict
num = int(input())
arr = list(map(int, input().split()))
mapping = defaultdict()
for (i, n) in enumerate(arr, start=1):
	mapping[i] = n
mx = max(mapping.keys())
cases = int(input())
while cases:
	cases -= 1
	(ind, k) = map(int, input().split())
	i = ind
	ans = 0
	while k and ind <= mx:
		if ind in mapping:
			if k < mapping[ind]:
				mapping[ind] -= k
				ans += k * (ind - i)
				break
			elif k == mapping[ind]:
				mapping.pop(ind)
				ans += k * (ind - i)
				if ind == mx:
					if mapping:
						mx = max(mapping.keys())
					else:
						mx = 0
				break
			else:
				k -= mapping[ind]
				ans += mapping[ind] * (ind - i)
				mapping.pop(ind)
				if ind == mx:
					if mapping:
						mx = max(mapping.keys())
					else:
						mx = 0
		else:
			ind += 1
	print(ans)


import sys
sys.setrecursionlimit(10 ** 8)

def findNext(v):
	if v == n + 1 or v == next[v]:
		return v
	next[v] = findNext(next[v])
	return next[v]
n = int(input())
P = [0] + list(map(int, input().split()))
next = [i for i in range(n + 1)]
q = int(input())
for qn in range(q):
	(x, k) = map(int, input().split())
	s = x
	total = 0
	while s <= n and k > 0:
		if P[s]:
			inc = min(k, P[s])
			P[s] -= inc
			k -= inc
			total += inc * (s - x)
			if not P[s]:
				next[s] = findNext(s + 1)
				s = next[s]
		else:
			s = findNext(s)
	findNext(x)
	print(total)


n = int(input())
a = list(map(int, input().split()))
b = [i for i in range(n)]
for q in range(int(input())):
	(s, k) = map(int, input().split())
	i = s - 1
	while b[i] != i:
		i = b[i]
	m = i
	p = i
	ans = 0
	while i < n and k:
		p = i
		if a[i] > k:
			ans += k * (i - s + 1)
			a[i] -= k
			k = 0
		elif a[i] == k:
			ans += k * (i - s + 1)
			a[i] = 0
			k = 0
		elif a[i] > 0:
			k -= a[i]
			ans += a[i] * (i - s + 1)
			a[i] = 0
		i += 1
	for j in range(m, p + 1):
		if a[j] == 0:
			b[j] = p
	print(ans)


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
sys.setrecursionlimit(100000 + 10)
tc = 1
for test in range(1, tc + 1):
	(n,) = inp()
	a = [0] + inp()
	par = [i for i in range(n + 1)]
	q = int(input())
	ans = [0]

	def find(ind, x, val):
		if par[x] != x:
			par[x] = find(ind, par[x], val)
		else:
			temp = min(val, a[x])
			ans[0] += temp * (x - ind)
			val -= temp
			a[x] -= temp
			if a[x] == 0:
				if x < n:
					par[x] = par[x + 1]
					if val > 0:
						par[x] = find(ind, par[x], val)
		return par[x]
	for i in range(q):
		ans[0] = 0
		(ind, val) = inp()
		find(ind, ind, val)
		print(ans[0])


n = int(input())
arr = list(map(int, input().split()))
to = [i + 1 for i in range(n)]
for _ in range(int(input())):
	(x, k) = map(int, input().split())
	x -= 1
	s = 0
	at = x
	while k > 0 and at < n:
		r = min(k, arr[at])
		arr[at] -= r
		k -= r
		s += r * (at - x)
		st = []
		while at < n and arr[at] == 0:
			st.append(at)
			at = to[at]
		while len(st) > 0:
			to[st.pop()] = at
	print(s)