from bisect import bisect_left, bisect_right, insort
from sortedcontainers import SortedList

class RangeMedianQuery:
    def __init__(self, A):
        self.A = A
        self.N = len(A)
        self.sl = SortedList()
        
    def update(self, i, x):
        self.A[i] = x  # 値の更新（SortedListも使うなら注意）

    def query_median(self, l, r):
        B = sorted(self.A[l:r+1])
        length = r - l + 1
        return B[(length - 1)//2]

# 入力読み込み例（実際のコンテストでは標準入力で）
N, Q = map(int, input().split())
A = list(map(int, input().split()))

query_processor = RangeMedianQuery(A)

for _ in range(Q):
    tmp = list(map(int, input().split()))
    if tmp[0] == 1:
        _, i, x = tmp
        query_processor.update(i - 1, x)
    else:
        _, l, r = tmp
        ans = query_processor.query_median(l - 1, r - 1)
        print(ans)