#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], ans[maxn];
int p;
int sz[maxn], cnt[maxn];
struct CHANGE {
  int pos, v;
};
struct REQ {
  int l, r, id, nowchange;
};
vector<CHANGE> change;
vector<REQ> req;
map<int, int> hs;
bool cmp(REQ ta, REQ tb) {
  return ta.l / p == tb.l / p
             ? (ta.r / p == tb.r / p ? ta.nowchange < tb.nowchange
                                     : ta.r / p < tb.r / p)
             : ta.l < tb.l;
}
template <class T>
inline void scan_d(T &ret) {
  char c;
  ret = 0;
  while ((c = getchar()) < '0' || c > '9')
    ;
  while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar();
}
template <class T>
inline void print_d(T x) {
  if (x > 9) print_d(x / 10);
  putchar(x % 10 + '0');
}
void update(int pos, int mode) {
  --sz[cnt[pos]];
  cnt[pos] += mode;
  ++sz[cnt[pos]];
}
void chn(int now, int l, int r) {
  if (l <= change[now].pos && r >= change[now].pos)
    update(a[change[now].pos], -1);
  swap(a[change[now].pos], change[now].v);
  if (l <= change[now].pos && r >= change[now].pos)
    update(a[change[now].pos], 1);
}
int wls() {
  int t = 0;
  while (++t)
    if (sz[t] == 0) return t;
}
void gao() {
  int l = 1, r = 1, now = 0;
  update(a[1], 1);
  for (auto it : req) {
    for (; r < it.r; ++r) update(a[r + 1], 1);
    for (; r > it.r; --r) update(a[r], -1);
    for (; l < it.l; ++l) update(a[l], -1);
    for (; l > it.l; --l) update(a[l - 1], 1);
    for (; now < it.nowchange; ++now) chn(now, l, r);
    for (; now > it.nowchange; --now) chn(now - 1, l, r);
    ans[it.id] = wls();
  }
}
int main() {
  int i, j, k, m, n, q;
  scan_d(n);
  scan_d(q);
  for (int i = 1; i <= n; ++i) {
    scan_d(a[i]);
    a[i] = hs.count(a[i]) ? hs[a[i]] : (hs[a[i]] = hs.size() + 1);
  }
  int mode, ta, tb;
  p = pow(n, 2 / 3);
  p = 3000;
  for (int i = 1; i <= q; ++i) {
    scan_d(mode);
    scan_d(ta);
    scan_d(tb);
    if (mode == 1) {
      int tc = req.size(), td = change.size();
      req.emplace_back(REQ{ta, tb, tc, td});
    } else {
      tb = hs.count(tb) ? hs[tb] : (hs[tb] = hs.size() + 1);
      change.emplace_back(CHANGE{ta, tb});
    }
  }
  sort(req.begin(), req.end(), cmp);
  gao();
  for (int i = 0; i < req.size(); ++i) {
    print_d(ans[i]);
    putchar('\n');
  }
  return 0;
}
