from math import isqrt
B=1500000

def enum_quot(n):
    x=isqrt(n)
    ret=list(range(1,x+1))
    for i in range(x,0,-1):
        if ret[-1]!=n//i:
            ret.append(n//i)
    return ret
        

N=int(input())
S=list(map(int,input().split()))
Q=int(input())
event=[tuple(map(int,input().split())) for i in range(Q)]
event.sort()
A=[]
now=0
end=0
for t,f in event:
    if now==0:
        end=f+t
        now=f
    else:
        if t<=end:
            end+=f
            now+=f
        else:
            A.append(now)
            end=f+t
            now=f
A.append(now)
small=[0]*B
large=[]
for a in A:
    quots=enum_quot(a)[::-1]
    quots.append(0)
    small[0]+=quots[0]
    for i in range(len(quots)-1):
        if a//quots[i]+1<B:
            small[a//quots[i]+1]+=quots[i+1]-quots[i]
        else:
            large.append((a//quots[i]+1,quots[i+1]-quots[i]))
large.append((1<<60,0))
large.sort(reverse=True)
fin=[0]*N
s=[(S[i],i) for i in range(N)]
s.sort()
for i in range(1,B):
    small[i]+=small[i-1]
now=small[-1]
for v,id in s:
    if v<B:
        fin[id]=small[v]
    else:
        while large[-1][0]<=v:
            now+=large[-1][1]
            large.pop()
        fin[id]=now
for i in fin:
    print(i)