class LazySegmentTree(): def __init__(self,n,init,merge=min,merge_unit=(10**18,-1),operate=lambda x,y:(x[0]+y,x[1]),operate_unit=0): self.merge=merge self.merge_unit=merge_unit self.operate=operate self.operate_unit=operate_unit self.n=(n-1).bit_length() 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_above(self,i): m=i.bit_length()-1 for bit in range(m,0,-1): v=i>>bit add=self.lazy[v] self.lazy[v]=self.operate_unit self.data[2*v]=self.operate(self.data[2*v],add) self.data[2*v+1]=self.operate(self.data[2*v+1],add) self.lazy[2*v]=self.lazy[2*v] + add self.lazy[2*v+1]=self.lazy[2*v+1] + add 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<>=1 r>>=1 self.remerge_above(l0) self.remerge_above(r0) def query(self,l,r): l+=1<>=1 r>>=1 return res import sys input = sys.stdin.readline N = int(input()) A = list(map(int,input().split())) def solve_not_one(): init = [0]*(N-1) Qsum = 0 for a in A: q = (a+1) // (N-1) r = (a+1) % (N-1) init[r] += 1 Qsum += q for i in range(1,N-1): init[i] += init[i-1] init = [(i-init[i],i) for i in range(N-1)] LST = LazySegmentTree(N-1,init) Q = int(input()) for _ in range(Q): query = tuple(map(int,input().split())) if query[0] == 1: gomi,i,x = query 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 else: q,r = LST.query(0,N-1) res = (N-1) * (Qsum + q) + r print(res) def solve_one(): Q = int(input()) for _ in range(Q): query = tuple(map(int,input().split())) if query[0] == 1: A[0] = query[2] else: print(A[0]+1) if N==1: solve_one() else: solve_not_one()