#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 123;
const long long INF = (long long)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;
void megaRandom() {
  unsigned int FOR;
  asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}
int n, m, c[N];
int last[N], block_id[N], pos[N], _next[N];
vector<int> g[400];
set<pair<int, int> > st[400];
pair<int, int> range[400];
int pref[400][400], in_arr[400][400];
void construct(int i) {
  int ptr = 0;
  pref[i][0] = 0;
  for (auto x : st[i]) {
    g[i][ptr] = x.first;
    if (ptr) pref[i][ptr] = pref[i][ptr - 1];
    pref[i][ptr] += x.first - x.second;
    ptr++;
  }
}
set<int> poss[N], posr[N];
int main() {
  megaRandom();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    poss[c[i]].insert(i);
    posr[c[i]].insert(-i);
  }
  for (int i = 1; i <= n; i++) last[i] = n + 1;
  for (int i = n; i >= 1; i--) {
    _next[i] = last[c[i]];
    if (last[c[i]] == n + 1) _next[i] = i;
    last[c[i]] = i;
  }
  int sqrtn = 320, cnt = 0, block = 1;
  for (int i = 1; i <= n; i++) {
    cnt++;
    block_id[i] = block;
    pos[i] = (int)(st[block].size());
    in_arr[block][pos[i]] = i;
    st[block].insert(make_pair(_next[i], i));
    if (cnt == sqrtn || i == n) {
      range[block] = make_pair(range[block - 1].second + 1, i);
      cnt = 0, block++;
    }
  }
  block--;
  for (int i = 1; i <= block; i++) {
    g[i].resize((int)(st[i].size()));
    construct(i);
  }
  for (int it = 1, type, x, y; it <= m; it++) {
    scanf("%d%d%d", &type, &x, &y);
    if (type == 1) {
      poss[c[x]].erase(x), posr[c[x]].erase(-x);
      auto tmp = posr[c[x]].upper_bound(-x);
      if (tmp != posr[c[x]].end()) {
        int ps = -*tmp;
        st[block_id[ps]].erase(make_pair(_next[ps], ps));
        if (poss[c[ps]].upper_bound(ps) != poss[c[ps]].end()) {
          _next[ps] = *poss[c[ps]].upper_bound(ps);
        } else
          _next[ps] = ps;
        st[block_id[ps]].insert(make_pair(_next[ps], ps));
        construct(block_id[ps]);
      }
      st[block_id[x]].erase(make_pair(_next[x], x));
      tmp = poss[y].upper_bound(x);
      if (tmp != poss[y].end())
        _next[x] = *tmp;
      else
        _next[x] = x;
      st[block_id[x]].insert(make_pair(_next[x], x));
      construct(block_id[x]);
      c[x] = y;
      poss[y].insert(x), posr[y].insert(-x);
      tmp = posr[y].upper_bound(-x);
      if (tmp != posr[y].end()) {
        int ps = -*tmp;
        st[block_id[ps]].erase(make_pair(_next[ps], ps));
        _next[ps] = x;
        st[block_id[ps]].insert(make_pair(_next[ps], ps));
        construct(block_id[ps]);
      }
    }
    if (type == 2) {
      long long res = 0;
      if (block_id[x] == block_id[y]) {
        for (int i = x; i <= y; i++)
          if (_next[i] <= y) res += _next[i] - i;
      } else {
        for (int i = x; i <= range[block_id[x]].second; i++)
          if (_next[i] <= y) res += _next[i] - i;
        for (int i = block_id[x] + 1; i <= block_id[y] - 1; i++) {
          if (g[i][0] > y) continue;
          int l = 0, r = (int)(g[i].size()) - 1;
          while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (g[i][mid] <= y)
              l = mid;
            else
              r = mid;
          }
          if (g[i][r] <= y) l = r;
          res += pref[i][l];
        }
        for (int i = range[block_id[y]].first; i <= y; i++)
          if (_next[i] <= y) res += _next[i] - i;
      }
      printf("%lld\n", res);
    }
  }
  return 0;
}
