class LazySegmentTree():
    def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.num = 1<<self.n
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        self.lazy[v]=self.operate_unit
        self.data[2*v]=self.operate(self.data[2*v],ope)
        self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
        self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
        self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

    def remerge_above(self,i):
        while i:
            i>>=1
            self.data[i]=self.operate(self.merge(self.data[2*i],self.data[2*i+1]),self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res

    def bisect_l(self,l,r,x):
        l += 1<<self.n
        r += 1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        Lmin = -1
        Rmin = -1
        while l<r:
            if l & 1:
                if self.data[l] <= x and Lmin==-1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.data[r-1] <=x:
                    Rmin = r-1
            l >>= 1
            r >>= 1

        res = -1
        if Lmin != -1:
            pos = Lmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            res =  pos-self.num
        if Rmin != -1:
            pos = Rmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            if res==-1:
                res = pos-self.num
            else:
                res = min(res,pos-self.num)

        return res


import sys,heapq
from operator import add

input = sys.stdin.readline

mask = (1<<20) -1

N = int(input())
assert(1<=N<=2*10**5)

A = list(map(int,input().split()))
assert(len(A)==N)
assert(all(0<=A[i]<=10**9 for i in range(N)))

def Divmod(val):
    x = val>>20
    y = val&mask
    return (x-N,y)

def solve_not_one():
    init = [0]*(N-1)
    Qsum = 0
    Max_que = []

    for i in range(N):
        a = A[i]
        q = (a+1) // (N-1)
        r = (a+1) % (N-1)
        init[r] += 1
        Qsum += q
        heapq.heappush(Max_que,(-a,i))

    for i in range(1,N-1):
        init[i] += init[i-1]

    init = [((i-init[i]+N)<<20)+i for i in range(N-1)]

    def operate(x,y):
        if y>=0:
            return x+(y<<20)
        else:
            return x-((-y)<<20)

    LST = LazySegmentTree(N-1,init,min,1<<60,operate,add,0)

    Q = int(input())
    assert(1<=Q<=10**5)

    for _ in range(Q):
        i,x = map(int,input().split())
        assert(1<=i<=N)
        assert(0<=x<=10**9)
        i -= 1

        #値の変更
        Qsum -= (A[i]+1) // (N-1)
        Qsum += (x+1) // (N-1)

        pre_r = (A[i]+1) % (N-1)
        LST.update(pre_r,N-1,1)

        next_r = (x+1) % (N-1)
        LST.update(next_r,N-1,-1)

        A[i] = x
        heapq.heappush(Max_que,(-x,i))

        #問題の答え
        while -Max_que[0][0] != A[Max_que[0][1]]:
            heapq.heappop(Max_que)

        lower = -Max_que[0][0] - (N-2)

        if lower<=0:
            print(0)
            continue

        lower_q = lower//(N-1)
        lower_r = lower%(N-1)

        t1_q,t1_r = Divmod(LST.query(0,lower_r))

        t2_q,t2_r = Divmod(LST.query(lower_r,N-1))

        res = min((t1_q + Qsum) * (N-1) + t1_r ,(t2_q + Qsum) * (N-1) +t2_r)
        print(res)


def solve_one():
    Q = int(input())
    assert(1<=Q<=10**5)
    for _ in range(Q):
        i,x = map(int,input().split())
        assert(1<=i<=N)
        assert(0<=x<=10**9)
        A[0] = x
        print(A[0]+1)

if N==1:
    solve_one()
else:
    solve_not_one()