import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    A = list(map(int, data[idx:idx+N]))
    idx += N
    Q = int(data[idx])
    idx += 1
    queries = []
    for _ in range(Q):
        i = int(data[idx])-1
        x = int(data[idx+1])
        queries.append((i, x))
        idx +=2
    
    c = N-2
    d = N-1
    x = [a - c for a in A]
    x_sorted = sorted(x)
    prefix = [0]*(N+1)
    for i in range(N):
        prefix[i+1] = prefix[i] + x_sorted[i]
    
    def compute_sum(m):
        res = 0
        for xi in x_sorted:
            if xi > m:
                break
            temp = (m - xi) // d
            res += temp
        return res
    
    for i, val in queries:
        A[i] = val
        x[i] = A[i] - c
        x_sorted = sorted(x)
        prefix = [0]*(N+1)
        for i in range(N):
            prefix[i+1] = prefix[i] + x_sorted[i]
        
        S = sum(A)
        m_min = max(0, S - N*(N-2))
        low = m_min
        high = m_min
        while True:
            s = compute_sum(high)
            if s >= high:
                break
            high += 1
        while low <= high:
            mid = (low + high) // 2
            s = compute_sum(mid)
            if s >= mid:
                high = mid -1
            else:
                low = mid +1
        print(low)

if __name__ == "__main__":
    main()