#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
const int maxn = 100010;
const int maxbit = 18;
const int sz = 1500;
inline int read() {
  int x = 0, f = 1;
  char ch = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
  return x * f;
}
struct node {
  int l, r, tid, ans, id;
  node() {}
  node(int _l, int _r, int _tid, int _ans, int _id) {
    l = _l;
    r = _r;
    tid = _tid;
    ans = _ans;
    id = _id;
  }
} que[maxn];
struct node2 {
  int p, fr, to;
  node2() {}
  node2(int _p, int _fr, int _to) {
    p = _p;
    fr = _fr;
    to = _to;
  }
} cz[maxn];
vector<int> oo;
inline int bl(int x) { return (x - 1) / sz; }
bool cmp(node x, node y) {
  if (bl(x.l) != bl(y.l))
    return x.l < y.l;
  else if (bl(x.r) != bl(y.r))
    return x.r < y.r;
  else
    return x.tid < y.tid;
}
bool cmp2(node x, node y) { return x.id < y.id; }
int n, q, cntz, cntq;
int a[maxn], fl[maxn], Now, L, R, cnt[maxn << 2];
inline void add(int x) {
  --fl[cnt[x]];
  ++fl[++cnt[x]];
}
inline void del(int x) {
  --fl[cnt[x]];
  ++fl[--cnt[x]];
}
inline void go(node2 &t) {
  if (t.p >= L && t.p <= R) del(t.fr), add(t.to);
  a[t.p] = t.to;
}
inline void re(node2 &t) {
  if (t.p >= L && t.p <= R) del(t.to), add(t.fr);
  a[t.p] = t.fr;
}
int main() {
  fl[0] = INF;
  n = read();
  q = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), oo.push_back(a[i]);
  for (int i = 1; i <= q; ++i) {
    int t = read();
    if (t == 1) {
      int l = read(), r = read();
      que[++cntq] = node(l, r, Now, 0, i);
    } else {
      int p = read(), x = read();
      oo.push_back(x);
      cz[++cntz] = node2(p, a[p], x);
      a[p] = x;
      ++Now;
    }
  }
  sort(oo.begin(), oo.end());
  int ss = unique(oo.begin(), oo.end()) - oo.begin();
  oo.resize(ss);
  for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(oo.begin(), oo.end(), a[i]) - oo.begin() + 1;
  for (int i = 1; i <= cntz; ++i) {
    cz[i].fr = lower_bound(oo.begin(), oo.end(), cz[i].fr) - oo.begin() + 1;
    cz[i].to = lower_bound(oo.begin(), oo.end(), cz[i].to) - oo.begin() + 1;
  }
  sort(que + 1, que + cntq + 1, cmp);
  for (int i = 1; i <= cntq; ++i) {
    node now = que[i];
    while (R < now.r) add(a[++R]);
    while (L > now.l) add(a[--L]);
    while (R > now.r) del(a[R--]);
    while (L < now.l) del(a[L++]);
    while (Now < now.tid) go(cz[++Now]);
    while (Now > now.tid) re(cz[Now--]);
    while (fl[que[i].ans]) ++que[i].ans;
  }
  sort(que + 1, que + cntq + 1, cmp2);
  for (int i = 1; i <= cntq; ++i) printf("%d\n", que[i].ans);
}
