#include <bits/stdc++.h>
using namespace std;
struct Query {
  int id, left, right, time, blockLeft, blockRight;
  Query()
      : id(-1), left(-1), right(-1), time(-1), blockLeft(-1), blockRight(-1) {}
  Query(int id, int left, int right, int time, int blockLeft, int blockRight)
      : id(id),
        left(left),
        right(right),
        time(time),
        blockLeft(blockLeft),
        blockRight(blockRight) {}
  bool operator<(const Query &otherQuery) const {
    if (blockLeft != otherQuery.blockLeft) {
      return blockLeft < otherQuery.blockLeft;
    }
    if (blockRight != otherQuery.blockRight) {
      return blockRight < otherQuery.blockRight;
    }
    return time < otherQuery.time;
  }
};
struct Operation {
  int pos, oldValue, newValue;
  Operation() : pos(-1), oldValue(-1), newValue(-1) {}
  Operation(int pos, int oldValue, int newValue)
      : pos(pos), oldValue(oldValue), newValue(newValue) {}
};
void del(int value, int *cnts, int *saveValues) {
  if (cnts[value] > 0) saveValues[cnts[value]]--;
  cnts[value]--;
  if (cnts[value] > 0) saveValues[cnts[value]]++;
}
void add(int value, int *cnts, int *saveValues) {
  if (cnts[value] > 0) saveValues[cnts[value]]--;
  cnts[value]++;
  if (cnts[value] > 0) saveValues[cnts[value]]++;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  int sqrtValue = pow(n, 2.0 / 3.0), *values = new int[n + 1],
      *tmpValues = new int[n + 1];
  if (sqrtValue == 0) sqrtValue = 1;
  vector<int> disValues;
  for (int i = 1; i <= n; i++) {
    cin >> values[i];
    tmpValues[i] = values[i];
    disValues.push_back(values[i]);
  }
  Query *querys = new Query[q + 1];
  Operation *opts = new Operation[q + 1];
  int cntQuerys = 0, cntOpts = 0;
  for (int i = 1; i <= q; i++) {
    int opt;
    cin >> opt;
    if (opt == 1) {
      int left, right;
      cin >> left >> right;
      ++cntQuerys;
      querys[cntQuerys] = Query(cntQuerys, left, right, cntOpts,
                                left / sqrtValue, right / sqrtValue);
    } else {
      int pos, value;
      cin >> pos >> value;
      ++cntOpts;
      opts[cntOpts] = Operation(pos, tmpValues[pos], value);
      tmpValues[pos] = value;
      disValues.push_back(value);
    }
  }
  sort(disValues.begin(), disValues.end());
  disValues.resize(unique(disValues.begin(), disValues.end()) -
                   disValues.begin());
  for (int i = 1; i <= cntOpts; i++) {
    Operation &tmpOpt = opts[i];
    tmpOpt.oldValue =
        lower_bound(disValues.begin(), disValues.end(), tmpOpt.oldValue) -
        disValues.begin();
    tmpOpt.newValue =
        lower_bound(disValues.begin(), disValues.end(), tmpOpt.newValue) -
        disValues.begin();
  }
  for (int i = 1; i <= n; i++) {
    values[i] = lower_bound(disValues.begin(), disValues.end(), values[i]) -
                disValues.begin();
  }
  int valueSize = static_cast<int>(disValues.size()),
      *cnts = new int[valueSize + 3], *saveValues = new int[n + 2];
  memset(cnts, 0, sizeof(int) * (valueSize + 3));
  memset(saveValues, 0, sizeof(int) * (n + 2));
  int *results = new int[cntQuerys + 1];
  sort(querys + 1, querys + cntQuerys + 1);
  int l = 1, r = 0, time = 0;
  for (int i = 1; i <= cntQuerys; i++) {
    Query &tmpQuery = querys[i];
    while (l > tmpQuery.left) {
      l--;
      add(values[l], cnts, saveValues);
    }
    while (l < tmpQuery.left) {
      del(values[l], cnts, saveValues);
      l++;
    }
    while (r > tmpQuery.right) {
      del(values[r], cnts, saveValues);
      r--;
    }
    while (r < tmpQuery.right) {
      r++;
      add(values[r], cnts, saveValues);
    }
    while (time < tmpQuery.time) {
      time++;
      Operation &tmpOpt = opts[time];
      if (tmpOpt.pos >= l && tmpOpt.pos <= r) {
        del(tmpOpt.oldValue, cnts, saveValues);
        add(tmpOpt.newValue, cnts, saveValues);
      }
      values[tmpOpt.pos] = tmpOpt.newValue;
    }
    while (time > tmpQuery.time) {
      Operation &tmpOpt = opts[time];
      if (tmpOpt.pos >= l && tmpOpt.pos <= r) {
        del(tmpOpt.newValue, cnts, saveValues);
        add(tmpOpt.oldValue, cnts, saveValues);
      }
      values[tmpOpt.pos] = tmpOpt.oldValue;
      time--;
    }
    for (int i = 1;; i++) {
      if (i > n) {
        results[tmpQuery.id] = 0;
      }
      if (saveValues[i] == 0) {
        results[tmpQuery.id] = i;
        break;
      }
    }
  }
  for (int i = 1; i <= cntQuerys; i++) {
    cout << results[i] << endl;
  }
  return 0;
}
