#include <bits/stdc++.h>
using namespace std;
namespace {
struct Op {
  int ty, a, b, id;
  void Read() { cin >> ty >> a >> b; }
};
const int MAX = 100111;
set<int> pos[MAX], orig[MAX];
int was[MAX];
long long bit[MAX];
int shape[MAX];
long long res[MAX];
int N;
void Add(int pos, int val) {
  for (int i = pos; i < MAX; i += i & -i) bit[i] += val;
}
int Get(int l, int r) {
  int res = 0;
  for (int i = r; i > 0; i -= i & -i) res += bit[i];
  for (int i = l - 1; i > 0; i -= i & -i) res -= bit[i];
  return res;
}
int Calc(const set<int>& vals, int l, int r) {
  if (vals.empty()) return 0;
  const int lst = *(--vals.upper_bound(r));
  const int fst = *vals.lower_bound(l);
  if (lst < l || fst > r) return 0;
  return lst - fst;
}
void Go(const vector<Op>& ops, const vector<Op>& all_ops) {
  vector<pair<int, int>> lef, rig;
  for (const auto& op : ops) {
    if (op.ty == 2) {
      lef.emplace_back(op.a, op.id);
      rig.emplace_back(op.b, op.id);
    }
  }
  sort(lef.rbegin(), lef.rend());
  sort(rig.begin(), rig.end());
  {
    memset(was, 0, sizeof(was));
    memset(bit, 0, sizeof(bit));
    int i = N;
    for (const auto& entry : lef) {
      while (i >= entry.first) {
        if (was[shape[i]]) Add(was[shape[i]], was[shape[i]]);
        Add(i, -i);
        was[shape[i]] = i;
        --i;
      }
      res[entry.second] += Get(entry.first, all_ops[entry.second].b);
    }
  }
  {
    memset(was, 0, sizeof(was));
    memset(bit, 0, sizeof(bit));
    int i = 1;
    for (const auto& entry : rig) {
      while (i <= entry.first) {
        if (was[shape[i]]) Add(was[shape[i]], -was[shape[i]]);
        Add(i, i);
        was[shape[i]] = i;
        ++i;
      }
      res[entry.second] += Get(all_ops[entry.second].a, entry.first);
    }
  }
  set<int> changed;
  for (const auto& op : ops) {
    if (op.ty == 1) {
      if (changed.insert(shape[op.a]).second) {
        orig[shape[op.a]] = pos[shape[op.a]];
      }
      if (changed.insert(op.b).second) {
        orig[op.b] = pos[op.b];
      }
      pos[shape[op.a]].erase(op.a);
      shape[op.a] = op.b;
      pos[shape[op.a]].insert(op.a);
    } else {
      for (const auto& s : changed) {
        res[op.id] -= Calc(orig[s], op.a, op.b);
        res[op.id] += Calc(pos[s], op.a, op.b);
      }
    }
  }
}
void Solve(long long test_num) {
  (void)test_num;
  int Q;
  cin >> N >> Q;
  for (auto i = (long long)(1); i < (long long)(N + 1); ++i) {
    cin >> shape[i];
    pos[shape[i]].insert(i);
  }
  vector<Op> ops(Q);
  for (auto q = (long long)(0); q < (long long)(Q); ++q) {
    ops[q].Read();
    ops[q].id = q;
  }
  memset(res, 0, sizeof(res));
  const int MAGIC = 312;
  for (int idx = 0; idx < Q; idx += MAGIC) {
    vector<Op> now;
    for (auto i = (long long)(0); i < (long long)(min(MAGIC, Q - idx)); ++i)
      now.push_back(ops[i]);
    Go(now, ops);
  }
  for (auto q = (long long)(0); q < (long long)(Q); ++q)
    if (ops[q].ty == 2) cout << res[q] << '\n';
}
void Init() {}
}  // namespace
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  srand(1223);
  Init();
  long long tests = 1;
  for (auto test = (long long)(1); test < (long long)(tests + 1); ++test) {
    Solve(test);
  }
  return 0;
}
