#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500001;
struct query {
  int l, r, k, id;
  query(int l_ = 0, int r_ = 0, int k_ = 0, int id_ = 0) {
    l = l_;
    r = r_;
    k = k_;
    id = id_;
  }
} q[MAXN];
struct change {
  int i, nxt;
  change(int i_ = 0, int nxt_ = 0) {
    i = i_;
    nxt = nxt_;
  }
} c[MAXN];
struct node {
  int key, id;
  node(int key_ = 0, int id_ = 0) {
    key = key_;
    id = id_;
  }
} a_[MAXN];
int n, K, q_, m, k, s, t, now, a[MAXN], vis[MAXN], re[MAXN], val[MAXN], o,
    x_[MAXN], y_[MAXN];
bool cmp(query x, query y) {
  if (x.l / K == y.l / K) {
    if (x.r / K == y.r / K) {
      return x.k < y.k;
    } else
      return x.r < y.r;
  } else
    return x.l < y.l;
}
bool cmp_a(node x, node y) { return x.key < y.key; }
void add(int x) {
  val[vis[a[x]]]--;
  vis[a[x]]++;
  val[vis[a[x]]]++;
}
void erase(int x) {
  val[vis[a[x]]]--;
  vis[a[x]]--;
  val[vis[a[x]]]++;
}
void chang(int now) {
  if (s <= c[now].i && c[now].i <= t) erase(c[now].i);
  swap(a[c[now].i], c[now].nxt);
  if (s <= c[now].i && c[now].i <= t) add(c[now].i);
}
int main() {
  scanf("%d%d", &n, &q_);
  K = pow(n, (double)2 / double(3));
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a_[i] = node(a[i], i);
  for (int i = 1; i <= q_; i++) {
    scanf("%d", &o);
    if (o == 1) {
      int l, r;
      scanf("%d%d", &l, &r);
      m++;
      q[m] = query(l, r, k, m);
    } else {
      k++;
      scanf("%d%d", &x_[k], &y_[k]);
      a_[n + k] = node(y_[k], n + k);
    }
  }
  sort(a_ + 1, a_ + 1 + n + k, cmp_a);
  int cnt = 0;
  for (int i = 1; i <= n + k; i++) {
    if (a_[i].key != a_[i - 1].key) cnt++;
    if (a_[i].id <= n)
      a[a_[i].id] = cnt;
    else
      y_[a_[i].id - n] = cnt;
  }
  for (int i = 1; i <= k; i++) c[i] = change(x_[i], y_[i]);
  sort(q + 1, q + 1 + m, cmp);
  s = 1;
  t = 0;
  now = 0;
  for (int i_ = 1; i_ <= m; i_++) {
    int i = q[i_].id, l = q[i_].l, r = q[i_].r, ti = q[i_].k;
    while (s < l) erase(s++);
    while (s > l) add(--s);
    while (t < r) add(++t);
    while (t > r) erase(t--);
    while (now < ti) chang(++now);
    while (now > ti) chang(now--);
    int ans = 1;
    while (val[ans]) ans++;
    re[i] = ans;
  }
  for (int i = 1; i <= m; i++) printf("%d\n", re[i]);
}
