#include #define _overload3(_1, _2, _3, name, ...) name #define _rep(i, n) repi(i, 0, n) #define repi(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__) #define ll long long #define lld long double #ifdef DEBUG #define line() cout << "[" << __LINE__ << "] "; #define dump(i) cout << #i ": " << i << " "; #define dumpl(i) cout << #i ": " << i << endl; #else #define line(i) #define dump(i) #define dumpl(i) #endif using namespace std; template struct SegmentTree { using F = function; int sz; vector seg; const F f; const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while (sz < n) sz *= 2; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k + sz] = x; } void build() { for (int k = sz - 1; k > 0; k++) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void update(int k, const Monoid &x) { k += sz; seg[k] = x; while (k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid query(int a, int b) { Monoid L = M1, R = M1; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) L = f(L, seg[a++]); if (b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } }; int f(int a, int b) { return min(a, b); } int main() { map mp; int N, Q; cin >> N >> Q; SegmentTree seg(N, f, INT_MAX); int a[N]; rep(i, N) { cin >> a[i]; a[i]--; seg.update(i, a[i]); mp[a[i]] = i; } rep(i, Q) { // rep(j, N) cerr << mp[j] << " "; // cerr << endl; int t, x, y; cin >> t >> x >> y; x--; y--; if (t == 1) { mp[a[x]] = y; mp[a[y]] = x; int tmp = a[x]; seg.update(x, a[y]); seg.update(y, tmp); a[y] = a[x]; a[x] = tmp; } else cout << mp[seg.query(x, y)] + 1 << endl; } return 0; }