#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <queue>
#include <deque>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <utility>
#include <fstream>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma comment(linker, "/STACK:256000000")
#pragma warning(disable:4996)

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll llinf = 1e18, mod = 1000'000'007ll;
const ld pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;

#define forn(i, n) for (int i = 0; i < (int)n; ++i)
#define firn(i, n) for (int i = 1; i < (int)n; ++i)
#define all(v) v.begin(), v.end()

template<typename T> bool uin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T> bool uax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }
template<class iterator> void output(iterator begin, iterator end, char p = ' ', ostream & out = cout) { while (begin != end) { out << (*begin) << p; begin++; } out << '\n'; }
template<class T> void output(T x, char p = ' ', ostream & out = cout) { output(all(x), p, out); }

mt19937 rnd(time(NULL));

int n;
int cnt[500'001], sq[710], pos[500'001];
void add(int a) {
	if (!cnt[a]) sq[pos[a]]--;
	cnt[a]++;
}
void del(int a) {
	cnt[a]--;
	if (!cnt[a]) sq[pos[a]]++;
}
int ansv() {
	int i = 0;
	for (; ; ++i)
		if (sq[i]) break;
	int j = 0, k = i * 710;
	for (; ; ++j)
		if (cnt[k + j] == 0) break;
	return j + k;
}
struct otr {
	int l, r, t, i;
};
int tt;
bool operator < (const otr & a, const otr & b) {
	if ((a.l / tt) != (b.l / tt))
		return a.l < b.l;
	if ((a.t / tt) != (b.t / tt))
		return a.t < b.t;
	if (1 & (a.t / tt))
		return a.r < b.r;
	return a.r > b.r;
}
struct chn {
	int	p, prev, x;
};
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int q;
	cin >> n >> q;
	tt = (int)pow((ld)n / 1.5, 0.66667);
	vector<int> a(n), b(n);
	forn(i, n) cin >> a[i], b[i] = a[i];
	vector<otr> ot;
	vector<chn> ch;
	vector<int> ans(q, -1);
	int time = 0;
	forn(i, q) {
		char tmp;
		cin >> tmp;
		if (tmp == '?') {
			int l, r;
			cin >> l >> r;
			l--; r--;
			ot.push_back(otr{ l, r, time, i });
		}
		else {
			int j, x;
			cin >> j >> x;
			j--;
			ch.push_back(chn{ j, b[j], x });
			b[j] = x;
			time++;
		}
	}
	sort(all(ot));
	int l = 0, r = -1, t = 0;
	forn(i, n + 1) pos[i] = i / 710, sq[i / 710]++;
	int p;
	forn(i, ot.size()) {
		for (; l > ot[i].l; --l) add(a[l - 1]);
		for (; r < ot[i].r; ++r) add(a[r + 1]);
		for (; l < ot[i].l; ++l) del(a[l]);
		for (; r > ot[i].r; --r) del(a[r]);
		for (; t < ot[i].t; ++t) {
			p = ch[t].p;
			if (p < l || p > r) {
				a[p] = ch[t].x;
			}
			else {
				del(a[p]);
				a[p] = ch[t].x;
				add(a[p]);
			}
		}
		for (; t > ot[i].t; --t) {
			p = ch[t - 1].p;
			if (p < l || p > r) {
				a[p] = ch[t - 1].prev;
			}
			else {
				del(a[p]);
				a[p] = ch[t - 1].prev;
				add(a[p]);
			}
		}
		ans[ot[i].i] = ansv();
	}
	forn(i, q)
		if (ans[i] > -1) cout << ans[i] << '\n';
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}