#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int nm = 0, fh = 1;
  char cw = getchar();
  for (; !isdigit(cw); cw = getchar())
    if (cw == '-') fh = -1;
  for (; isdigit(cw); cw = getchar()) nm = nm * 10 + (cw - '0');
  return nm * fh;
}
int n, Q, K, a[200020], blg[200020], num[200020], len, T[200020], L, R, nowtms;
int top, tail, cnt[200020], ans[200020];
pair<int, int> sta[200020];
struct Query {
  int x, y, tms, id;
} que[200020];
inline bool cmp(Query a, Query b) {
  if (blg[a.x] ^ blg[b.x]) return blg[a.x] < blg[b.x];
  if (blg[a.y] ^ blg[b.y]) return blg[a.y] < blg[b.y];
  return a.tms < b.tms;
}
inline void ins(int x) {
  if (cnt[x]) --T[cnt[x]];
  cnt[x]++, T[cnt[x]]++;
}
inline void ers(int x) {
  --T[cnt[x]], --cnt[x];
  if (cnt[x]) T[cnt[x]]++;
}
inline void chg(int now) {
  int x = sta[now].first;
  if (L <= x && x <= R) ers(a[x]);
  swap(sta[now].second, a[x]);
  if (L <= x && x <= R) ins(a[x]);
}
inline int getmex() {
  for (int i = 1;; i++)
    if (!T[i]) return i;
}
int main() {
  n = read(), Q = read(), K = pow(n, 0.666666);
  for (int i = 1; i <= n; i++)
    a[i] = read(), num[++len] = a[i], blg[i] = (i - 1) / K + 1;
  for (int i = 1, op, x, y; i <= Q; i++) {
    op = read(), x = read(), y = read();
    if (op == 1)
      top++, que[top] = (Query){x, y, tail, top};
    else
      sta[++tail] = make_pair(x, y), num[++len] = y;
  }
  sort(num + 1, num + len + 1), len = unique(num + 1, num + len + 1) - num - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(num + 1, num + len + 1, a[i]) - num;
  for (int i = 1; i <= tail; i++)
    sta[i].second = lower_bound(num + 1, num + len + 1, sta[i].second) - num;
  sort(que + 1, que + top + 1, cmp);
  L = 1, R = nowtms = 0;
  for (int i = 1; i <= top; i++) {
    while (L > que[i].x) ins(a[--L]);
    while (R < que[i].y) ins(a[++R]);
    while (L < que[i].x) ers(a[L++]);
    while (R > que[i].y) ers(a[R--]);
    while (nowtms < que[i].tms) chg(++nowtms);
    while (nowtms > que[i].tms) chg(nowtms--);
    ans[que[i].id] = getmex();
  }
  for (int i = 1; i <= top; i++) printf("%d\n", ans[i]);
  return 0;
}
