#include <bits/stdc++.h>
using namespace std;
const int maxm = 1.5e7;
const int maxn = 1e5 + 5;
int lson[maxm], rson[maxm];
long long sum[maxm];
int T[maxn];
int clk, n;
void modity(int &rt, int L, int R, int pos, int val) {
  if (!rt) rt = ++clk;
  if (L == R) {
    sum[rt] += val;
  } else {
    int mid = L + R >> 1;
    if (pos <= mid)
      modity(lson[rt], L, mid, pos, val);
    else
      modity(rson[rt], mid + 1, R, pos, val);
    sum[rt] = sum[lson[rt]] + sum[rson[rt]];
  }
}
long long query(int rt, int L, int R, int l, int r) {
  if (!rt) return 0;
  if (l <= L && R <= r)
    return sum[rt];
  else {
    int mid = L + R >> 1;
    long long ret = 0;
    if (l <= mid) ret += query(lson[rt], L, mid, l, r);
    if (mid < r) ret += query(rson[rt], mid + 1, R, l, r);
    return ret;
  }
}
int lowbit(int x) { return x & -x; }
void modity(int pos, pair<int, int> val) {
  for (int i = pos; i <= n; i += lowbit(i)) {
    modity(T[i], 1, n, val.first, val.second);
  }
}
long long query(int l, int r) {
  long long ret = 0;
  for (int i = r; i > 0; i -= lowbit(i)) ret += query(T[i], 1, n, l, n);
  for (int i = l - 1; i > 0; i -= lowbit(i)) ret -= query(T[i], 1, n, l, n);
  return ret;
}
set<int> s[maxn];
int a[maxn];
int main() {
  int m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (s[a[i]].size()) {
      int prev = *s[a[i]].rbegin();
      modity(i, make_pair(prev, i - prev));
    }
    s[a[i]].insert(i);
  }
  while (m--) {
    int opt;
    scanf("%d", &opt);
    if (opt == 1) {
      int pos, val;
      scanf("%d %d", &pos, &val);
      if (val == a[pos]) continue;
      auto it = s[a[pos]].find(pos);
      auto is = it;
      it++;
      if (it != s[a[pos]].end()) {
        modity(*it, make_pair(*is, *is - *it));
        if (is != s[a[pos]].begin()) {
          auto ix = is;
          ix--;
          modity(*it, make_pair(*ix, *it - *ix));
        }
      }
      if (is != s[a[pos]].begin()) {
        auto ix = is;
        ix--;
        modity(*is, make_pair(*ix, *ix - *is));
      }
      s[a[pos]].erase(pos);
      a[pos] = val;
      is = s[a[pos]].insert(pos).first;
      if (is != s[a[pos]].begin()) {
        auto ix = is;
        ix--;
        modity(*is, make_pair(*ix, *is - *ix));
      }
      it = is;
      it++;
      if (it != s[a[pos]].end()) {
        if (is != s[a[pos]].begin()) {
          auto ix = is;
          ix--;
          modity(*it, make_pair(*ix, *ix - *it));
        }
        modity(*it, make_pair(*is, *it - *is));
      }
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      long long ret = query(l, r);
      printf("%lld\n", ret);
    }
  }
  return 0;
}
