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<>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<>=1 r>>=1 self.remerge_above(l0) self.remerge_above(r0) def query(self,l,r): l+=1<>=1 r>>=1 return res def bisect_l(self,l,r,x): l += 1<>= 1 r >>= 1 res = -1 if Lmin != -1: pos = Lmin while pos>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()) for _ in range(Q): i,x = map(int,input().split()) 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)) if t1_r != -1 and t1_q + Qsum <= lower_q: t1_q, t1_r = lower_q+1-Qsum, LST.bisect_l(0,lower_r,-1+((lower_q+2-Qsum + N)<<20)) t2_q,t2_r = Divmod(LST.query(lower_r,N-1)) if t2_r != -1 and t2_q + Qsum < lower_q: t2_q,t2_r = lower_q-Qsum,LST.bisect_l(lower_r,N-1,-1+((lower_q+1-Qsum + N)<<20)) 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())) i,x = map(int,input().split()) A[0] = x print(A[0]+1) if N==1: solve_one() else: solve_not_one()