Untitled

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> a;
vector<int> arr, idxs;

class segtree {
private:
	vector<int> tree;
	void build(int s, int e, int node) {
		if (s == e)
			tree[node] = arr[s];
		else {
			int mid = (s + e) / 2;
			build(s, mid, node * 2);
			build(mid + 1, e, node * 2 + 1);
			tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
		}
	}

	int rmq(int s, int e, int node, int l, int r) {
		if ((r < s) || (l > e)) return 1e9;
		if ((l <= s) && (r >= e)) return tree[node];
		int mid = (s + e) / 2;
		return min(rmq(s, mid, node * 2, l, r), rmq(mid + 1, e, node * 2 + 1, l, r));
	}

	void update(int s, int e, int node, int idx, int val) {
		if ((idx < s) || (idx > e)) return;
		if (s == e) tree[node] = arr[s] = val;
		else {
			int mid = (s + e) / 2;
			update(s, mid, node * 2, idx, val);
			update(mid + 1, e, node * 2 + 1, idx, val);
			tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
		}
	}

public:
	int query(int l, int r) {
		auto res = rmq(0, arr.size() - 1, 1, l, r);
		return (res == 1e9 ? -1 : res);
	}
	void update(int idx, int val) {
		update(0, arr.size() - 1, 1, idx, val);
	}
	segtree(int n) {
		tree.resize(4 * n);
		build(0, n - 1, 1);
	}
};

int main()
{
	int n, m; cin >> n >> m;
	a.resize(n), idxs.resize(n);
	for (int i = 0; i < n; ++i) cin >> a[i].first;
	for (int i = 0; i < n; ++i) a[i].second = i;
	sort(a.begin(), a.end());
	for (auto x : a) arr.push_back(x.second);
	for (int i = 0; i < n; ++i) idxs[a[i].second] = i;
	segtree s(n);

	while (m--) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 0) {
			auto it = lower_bound(a.begin(), a.end(), make_pair(x, -1));
			if (it == a.end()) { cout << -1 << endl; continue; }
			auto it2 = lower_bound(a.begin(), a.end(), make_pair(y, (int)1e9));
			if (it2 == a.begin()) { cout << -1 << endl; continue; }
			x = idxs[(*it).second], y = idxs[(*(it2 - 1)).second];
			cout << s.query(x, y) << endl;
		}
		else {
			s.update(idxs[x], y);
			s.update(idxs[y], x);
			a[idxs[x]].second = y;
			a[idxs[y]].second = x;
			swap(idxs[x], idxs[y]);
		}
	}
}