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,heapq input = sys.stdin.readline N = int(input()) A = list(map(int,input().split())) 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],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 heapq.heappush(Max_que,(-x,i)) else: 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 = LST.query(0,lower_r) if t1_r != -1 and t1_q + Qsum <= lower_q: start = -1 end = lower_r-1 while end-start>1: test = (end + start) // 2 if LST.query(0,test+1)[0] + Qsum <= lower_q: end = test else: start = test t1_q, t1_r = lower_q+1-Qsum, end t2_q,t2_r = LST.query(lower_r,N-1) if t2_r != -1 and t2_q + Qsum < lower_q: start = lower_r-1 end = N-2 while end-start>1: test = (end + start) // 2 if LST.query(lower_r,test+1)[0] + Qsum < lower_q: end = test else: start = test t2_q,t2_r = lower_q-Qsum,end res = min((t1_q + Qsum) * (N-1) + t1_r ,(t2_q + Qsum) * (N-1) +t2_r) assert(res>=lower) 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) def brute_force(): def solve(): R = [0]*(N-1) Qsum = 0 for a in A: q = (a+1)//(N-1) r = (a+1)%(N-1) Qsum += q R[r] += 1 for i in range(1,N-1): R[i] += R[i-1] Amax = max(A) lower = Amax - (N-2) Qmax = lower // (N-1) Rmax = lower % (N-1) if lower<=0: return 0 res = 10**18 for r in range(N-1): if r