class SegmentTree # n is the size of array or array itself def initialize(n, unity, &func) raise ArgumentError if !n || !unity || !block_given? @size_r = 1 @n = (n.is_a?(Array) ? n.size : n) while @size_r < @n @size_r <<= 2 end @func = func @unity = unity @data = Array.new(@size_r * 2, @unity) if n.is_a?(Array) @n.times { |i| @data[i + @size_r] = n[i] } self.build() end end # set value at index, index is 0-indexed def set(index, value) raise IndexError if index >= @n @data[index + @size_r] = value end def build (@size_r - 1).downto(1) do |k| @data[k] = @func.call(@data[k * 2], @data[k * 2 + 1]) end end # update the previous value at index to value, index is 0-indexed def update(index, value) raise IndexError if index >= @n index += @size_r @data[index] = value index >>= 1 while index > 0 @data[index] = @func.call(@data[index * 2], @data[index * 2 + 1]) index >>= 1 end true end # get [a, b), a and b are 0-indexed def get(a, b) raise IndexError if a >= @n || b > @n || a > b vleft = vright = @unity left = a + @size_r right = b + @size_r while (left < right) if (left & 1) == 1 vleft = @func.call(vleft, @data[left]) left += 1 end if (right & 1) == 1 right -= 1 vright = @func.call(@data[right], vright) end left >>= 1 right >>= 1 end return @func.call(vleft, vright) end def [](k) @data[@size_r + k] end end N, q = gets.split.map(&:to_i) a = gets.split.map(&:to_i) h = {} seg = SegmentTree.new(N, 1 << 31) { |x, y| x > y ? y : x } N.times do |i| h[a[i]] = i seg.set(i, a[i]) end seg.build() ans = [] q.times do c, l, r = gets.split.map(&:to_i) l -= 1 r -= 1 if c == 1 tmpl = seg[l] tmpr = seg[r] seg.update(l, tmpr) seg.update(r, tmpl) h[tmpr] = l h[tmpl] = r else ans << h[seg.get(l, r + 1)] + 1 end end puts ans