# coding: utf-8 # Your code here! """ セグメント木(一般化) """ class segment_tree: """ N: 処理する区間の長さ """ def __init__(self, N): #演算子および単位元を定義する。 # max, min, __add__,ラムダ式,関数定義... self.op = min self.UNIT = (1<<32)-1 self.N0 = 2**(N-1).bit_length() self.tree = [self.UNIT]*(2*self.N0) # a_k の値を x に更新 def update(self, k,x): k += self.N0-1 self.tree[k] = x while k >= 0: k = (k - 1) // 2 self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2]) # 区間[l,r]をopでまとめる def query(self, l,r): L = l + self.N0; R = r + self.N0 + 1 s = self.UNIT while L < R: if R & 1: R -= 1 s = self.op(s, self.tree[R-1]) if L & 1: s = self.op(s, self.tree[L-1]) L += 1 L >>= 1; R >>= 1 return s def get(self, k): #k番目の値を取得。query[k,k]と同じ return self.tree[k+self.N0-1] import sys sys.setrecursionlimit(10**6) readline = sys.stdin.readline n,q = [int(i) for i in readline().split()] a = [int(i)-1 for i in readline().split()] ilr = [[int(i) for i in readline().split()] for i in range(q)] seg = segment_tree(n) ra = [0]*(n) for i,ai in enumerate(a): seg.update(i,ai) ra[ai] = i for i,l,r in ilr: l -= 1 r -= 1 if i == 1: al = seg.get(l) ar = seg.get(r) seg.update(l,ar) seg.update(r,al) # print(al,ar,"al,ar") a[l],a[r]=a[r],a[l] ra[al],ra[ar] = ra[ar],ra[al] # print(ra) else: m = seg.query(l,r) print(ra[m]+1)