#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], type, l, r;
set<int> q[N];
inline int myrand() { return rand() ^ (rand() << 16); }
struct item {
  item *l, *r;
  int key, prior, val;
  long long sum;
  item() {}
  item(int _key, int _val) {
    val = sum = _val;
    key = _key;
    prior = myrand();
    l = r = nullptr;
  }
};
typedef item *pitem;
pitem t[4 * N];
inline long long sum(pitem v) { return v ? v->sum : 0; }
inline void upd_cnt(pitem v) {
  if (v) {
    v->sum = sum(v->l) + v->val + sum(v->r);
  }
}
void Merge(pitem &v, pitem l, pitem r) {
  if (!l || !r) {
    v = l ? l : r;
  } else if (l->prior > r->prior) {
    Merge(l->r, l->r, r);
    v = l;
  } else {
    Merge(r->l, l, r->l);
    v = r;
  }
  upd_cnt(v);
}
void Split(pitem v, int key, pitem &l, pitem &r) {
  if (!v) {
    l = r = nullptr;
    return;
  }
  if (key < v->key) {
    Split(v->l, key, l, v->l);
    r = v;
  } else {
    Split(v->r, key, v->r, r);
    l = v;
  }
  upd_cnt(v);
}
void Insert(pitem &v, int key, int val) {
  pitem cur;
  Split(v, key, v, cur);
  Merge(v, v, new item(key, val));
  Merge(v, v, cur);
}
void Erase(pitem &v, int key) {
  if (!v) {
    cout << "SOSI";
    exit(0);
  }
  if (v->key == key) {
    pitem sosi = v;
    Merge(v, v->l, v->r);
    delete sosi;
    return;
  }
  Erase(key < v->key ? v->l : v->r, key);
  upd_cnt(v);
}
void update(int pos, int key, int val, int add) {
  for (int i = pos; i <= n; i |= i + 1) {
    if (add == 1) {
      Insert(t[i], key, val);
    } else {
      Erase(t[i], key);
    }
  }
}
inline long long Get(pitem v, int l, int r) {
  pitem cur1, cur2;
  Split(v, l - 1, v, cur1);
  Split(cur1, r, cur1, cur2);
  long long ans = sum(cur1);
  Merge(v, v, cur1);
  Merge(v, v, cur2);
  return ans;
}
long long get(int pos, int tl, int tr) {
  long long ans = 0;
  for (int i = pos; i >= 1; i &= i + 1, i--) {
    ans += Get(t[i], tl, tr);
  }
  return ans;
}
int main() {
  srand(time(nullptr));
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    q[i].insert(-1e9);
    t[i] = nullptr;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    int prv = *(--q[a[i]].insert(i).first);
    update(i, prv, i - prv, +1);
  }
  for (int i = 1; i <= m; i++) {
    cin >> type >> l >> r;
    if (type == 1) {
      auto it = q[a[l]].find(l);
      int prv = *prev(it);
      it = next(it);
      update(l, prv, -1, -1);
      if (it != q[a[l]].end()) {
        int nxt = *it;
        update(nxt, l, -1, -1);
        update(nxt, prv, nxt - prv, +1);
      }
      q[a[l]].erase(l);
      a[l] = r;
      it = q[a[l]].insert(l).first;
      prv = *prev(it);
      it = next(it);
      if (it != q[a[l]].end()) {
        int nxt = *it;
        update(nxt, prv, -1, -1);
        update(nxt, l, nxt - l, +1);
      }
      update(l, prv, l - prv, +1);
    } else {
      cout << get(r, l, r) - get(l - 1, l, r) << "\n";
    }
  }
}
