class LazySegTree: # RMQ and RAQ def __init__(self, init_val, seg_ide, lazy_ide, segfunc): self.n = len(init_val) self.num = 2**(self.n-1).bit_length() self.seg_ide = seg_ide self.lazy_ide = lazy_ide self.segfunc = segfunc # seg, lazy: 1-indexed self.seg = [seg_ide]*2*self.num for i in range(self.n): self.seg[i+self.num] = init_val[i] for i in range(self.num-1, 0, -1): self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1]) self.lazy = [lazy_ide]*2*self.num def gindex(self, l, r): # l, r: 1-indexed L = l + self.num R = r + self.num lm = (L // (L & -L)) >> 1 rm = (R // (R & -R)) >> 1 while L < R: if R <= rm: yield R if L <= lm: yield L L = L >> 1 R = R >> 1 while L: yield L L = L >> 1 def propagate(self, *ids): # ids: 1-indexed for i in reversed(ids): v = self.lazy[i] if v == self.lazy_ide: continue self.lazy[2*i] += v self.lazy[2*i+1] += v self.seg[2*i] += v self.seg[2*i+1] += v self.lazy[i] = self.lazy_ide def update(self, l, r, x): # l, r: 0-indexed # add x to [l, r) L = l + self.num R = r + self.num while L < R: if R & 1: R -= 1 self.lazy[R] += x self.seg[R] += x if L & 1: self.lazy[L] += x self.seg[L] += x L += 1 L = L >> 1 R = R >> 1 for i in self.gindex(l, r): # i: 1-indexed self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1]) + self.lazy[i] def query(self, l, r): # l, r: 0-indexed # query for [l, r) if r <= l: return self.seg_ide self.propagate(*self.gindex(l, r)) L = l + self.num R = r + self.num res = self.seg_ide while L < R: if R & 1: R -= 1 res = self.segfunc(res, self.seg[R]) if L & 1: res = self.segfunc(self.seg[L], res) L += 1 L = L >> 1 R = R >> 1 return res def __str__(self): # for debug arr = [self.query(i,i+1) for i in range(self.n)] return str(arr) import sys import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline from itertools import accumulate def main(): n = int(input()) A = list(map(int, input().split())) C = [0]+A C = list(accumulate(C)) B = [] for i in range(n): if i+24 <= n: b = C[i+24]-C[i] B.append(b) seg = LazySegTree(B, -1, 0, max) q = int(input()) for i in range(q): t, v = map(int, input().split()) t -= 1 p = A[t] seg.update(max(0, t-24), min(seg.n, t+1), -p+v) A[t] = v print(seg.query(0, seg.n)) if __name__ == '__main__': main()