def read_gen(fname):
with open(fname, 'rt') as fin:
for line in fin:
for val in line.split():
yield int(val)
def build(a, v, st, dr, pos):
if st == dr:
a[pos] = v[st]
else:
mid = (st + dr) // 2
build(a, v, st, mid, pos * 2)
build(a, v, mid + 1, dr, pos * 2 + 1)
a[pos] = max(a[pos * 2], a[pos * 2 + 1])
def change(a, nv, pnv, st, dr, pos):
if st == dr:
a[pos] = nv
else:
mid = (st + dr) // 2
if pnv <= mid:
change(a, nv, pnv, st, mid, pos * 2)
else:
change(a, nv, pnv, mid + 1, dr, pos * 2 + 1)
a[pos] = max(a[pos * 2], a[pos * 2 + 1])
def find_max(a, pos, i_left, i_right, c_left, c_right):
if c_left >= i_left and c_right <= i_right:
return a[pos]
else:
mid = (c_left + c_right) // 2
s_value = 0
if i_left <= mid:
s_value = find_max(a, pos * 2, i_left, i_right, c_left, mid)
if mid + 1 <= i_right:
s_value = max(s_value, find_max(a, pos * 2 + 1, i_left, i_right, mid + 1, c_right))
return s_value
if __name__ == "__main__":
it = read_gen("arbint.in")
n, m = next(it), next(it)
v = [0] + [next(it) for _ in range(n)]
a = [0 for _ in range((n + 1) * 4 + 1)]
""" a[i] = maxmimum if an interval (defined by the subintervals) """
build(a, v, 1, n, 1)
with open('arbint.out', 'wt') as fout:
for _ in range(m):
t, x, y = next(it), next(it), next(it)
if t == 0:
maxv = find_max(a, 1, x, y, 1, n)
fout.write('{}\n'.format(maxv))
elif t == 1:
change(a, y, x, 1, n, 1)