#include <bits/stdc++.h>
using namespace std;
int blk = 2000;
int n, q, a[100005], init[100005], qq, qu, ct[200005], pres[200005];
pair<pair<int, int>, int> upd[100005];
pair<pair<int, int>, pair<int, int> > qr[100005];
bool cmp(pair<pair<int, int>, pair<int, int> > p1,
         pair<pair<int, int>, pair<int, int> > p2) {
  if (p1.first.first / blk != p2.first.first / blk)
    return p1.first.first / blk < p2.first.first / blk;
  if (p1.first.second / blk != p2.first.second / blk)
    return p1.first.second / blk < p2.first.second / blk;
  return p1.second.first < p2.second.first;
}
int cl, cr, curtime;
void rmv(int ps) {
  if (ps == 0 || ps > n) return;
  int v = ps;
  pres[ct[a[v]]]--;
  ct[a[v]]--;
  pres[ct[a[v]]]++;
}
void add(int ps) {
  if (ps == 0 || ps > n) return;
  int v = ps;
  pres[ct[a[v]]]--;
  ct[a[v]]++;
  pres[ct[a[v]]]++;
}
int res[200005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  set<int> vals;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i], vals.insert(a[i]), init[i] = a[i];
  set<int> aff;
  for (int i = 1; i <= q; ++i) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      int l, r;
      cin >> l >> r;
      qq++;
      qr[qq] = make_pair(make_pair(l, r), make_pair(qu, qq));
    } else {
      int p, x;
      cin >> p >> x;
      vals.insert(x);
      aff.insert(p);
      upd[++qu] = make_pair(make_pair(p, x), a[p]);
      a[p] = x;
    }
  }
  if (!qq) return 0;
  map<int, int> comp;
  int st = 0;
  for (int v : vals) comp[v] = ++st;
  for (int i = 1; i <= n; ++i) a[i] = comp[init[i]], init[i] = a[i];
  for (int i = 1; i <= qu; ++i)
    upd[i].first.second = comp[upd[i].first.second],
    upd[i].second = comp[upd[i].second];
  sort(qr + 1, qr + qq + 1, cmp);
  for (int i = 1; i <= qq; ++i) {
    int l = qr[i].first.first, r = qr[i].first.second, tt = qr[i].second.first,
        ind = qr[i].second.second;
    while (tt < curtime) {
      int v = upd[curtime].first.first;
      if (v >= cl && v <= cr) {
        pres[ct[a[v]]]--;
        ct[a[v]]--;
        pres[ct[a[v]]]++;
        a[v] = upd[curtime].second;
        pres[ct[a[v]]]--;
        ct[a[v]]++;
        pres[ct[a[v]]]++;
      } else
        a[v] = upd[curtime].second;
      curtime--;
    }
    while (curtime < tt) {
      curtime++;
      int v = upd[curtime].first.first;
      if (v >= cl && v <= cr) {
        pres[ct[a[v]]]--;
        ct[a[v]]--;
        pres[ct[a[v]]]++;
        a[v] = upd[curtime].first.second;
        pres[ct[a[v]]]--;
        ct[a[v]]++;
        pres[ct[a[v]]]++;
      } else
        a[v] = upd[curtime].first.second;
    }
    while (cl < l) rmv(cl), cl++;
    while (cl > l) add(cl - 1), cl--;
    while (cr < r) add(cr + 1), cr++;
    while (cr > r) rmv(cr), cr--;
    int ans = 1;
    while (pres[ans]) ans++;
    res[ind] = ans;
  }
  for (int i = 1; i <= qq; ++i) cout << res[i] << '\n';
}
