class SegmentTree def initialize(n, inf = (1 << 30) - 1 + (1 << 30), &func) @n = n, @l = 1, @inf = inf while @l < n @l <<= 1 end @data = Array.new(@l * 2, @inf) if block_given? @func = func else @func = lambda { |a, b| a > b ? b : a } end end def update(i, x) i += @l @data[i] = x i >>= 1 while i > 0 @data[i] = @func.call(@data[i * 2], @data[i * 2 + 1]) i >>= 1 end true end # minimum of [l, r) def query(l, r) _query(l, r, 1, 0, @l) end def [](k) @data[@l + k] end private def _query(l, r, k, sl, sr) return @inf if sr <= l || r <= sl return @data[k] if l <= sl && sr <= r dl = _query(l, r, k * 2, sl, (sl + sr) / 2) dr = _query(l, r, k * 2 + 1, (sl + sr) / 2, sr) @func.call(dl, dr) end end h = {} n, q = gets.split.map(&:to_i) a = gets.split.map(&:to_i) rmq = SegmentTree.new(n) { |x, y| x > y ? y : x } n.times do |i| h[a[i]] = i rmq.update(i, a[i]) end ans = [] q.times do c, l, r = gets.split.map(&:to_i) l -= 1 r -= 1 if c == 1 tmpl = rmq[l] tmpr = rmq[r] rmq.update(l, tmpr) rmq.update(r, tmpl) h[tmpr] = l h[tmpl] = r else ans << h[rmq.query(l, r + 1)] + 1 end end puts ans