#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3 * 100 * 1000 + 17;
int n, q, S, a[MAXN], ans[MAXN], cnt, m, b[MAXN], c[MAXN], st = 1, en, tnow;
vector<int> num[MAXN];
pair<int, int> upd[MAXN];
pair<pair<int, int>, pair<int, int> > qr[MAXN];
bool cmp_mo(pair<pair<int, int>, pair<int, int> > A,
            pair<pair<int, int>, pair<int, int> > B) {
  if (A.first.first / S != B.first.first / S)
    return A.first.first < B.first.first;
  if (A.first.second / S != B.first.second / S)
    return A.first.second < B.first.second;
  return A.second.first < B.second.first;
}
void compress() {
  vector<int> all;
  for (int i = 1; i <= n; i++) all.push_back(a[i]);
  for (int i = 1; i <= cnt; i++) all.push_back(upd[i].second);
  sort(all.begin(), all.end());
  all.resize(unique(all.begin(), all.end()) - all.begin());
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin() + 1;
  for (int i = 1; i <= cnt; i++)
    upd[i].second =
        lower_bound(all.begin(), all.end(), upd[i].second) - all.begin() + 1;
}
void change(int x, int val) {
  if (x == 0) return;
  b[c[x]]--;
  c[x] += val;
  b[c[x]]++;
}
void undo(int updNUM) {
  int x = upd[updNUM].first;
  if (st <= x && x <= en) change(num[x].back(), -1);
  num[x].pop_back();
  if (st <= x && x <= en) change(num[x].back(), 1);
}
void do_upd(int updNUM) {
  int x = upd[updNUM].first, val = upd[updNUM].second;
  if (st <= x && x <= en) change(num[x].back(), -1);
  num[x].push_back(val);
  if (st <= x && x <= en) change(num[x].back(), 1);
}
void add(int x, int val) { change(num[x].back(), val); }
int get() {
  for (int i = 1;; i++)
    if (!b[i]) return i;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  S = cbrt(n) * cbrt(n);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= q; i++) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 2)
      upd[++cnt] = {x, y};
    else {
      ++m;
      qr[m] = {{x, y}, {cnt, m}};
    }
  }
  compress();
  for (int i = 1; i <= n; i++) num[i].push_back(a[i]);
  sort(qr + 1, qr + m + 1, cmp_mo);
  for (int i = 1; i <= m; i++) {
    while (tnow < qr[i].second.first) do_upd(++tnow);
    while (tnow > qr[i].second.first) undo(tnow--);
    while (en < qr[i].first.second) add(++en, 1);
    while (en > qr[i].first.second) add(en--, -1);
    while (st < qr[i].first.first) add(st++, -1);
    while (st > qr[i].first.first) add(--st, 1);
    ans[qr[i].second.second] = get();
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << endl;
  return 0;
}
