#include <bits/stdc++.h>
using namespace std;
int n, m, x[100005], q[100005], cnt, ta, tb, tc, td;
set<int> s[100005];
set<int>::iterator it;
pair<int, pair<int, int> > v[700005], tv[700005];
long long w[18][100005], ans[100005];
long long f1(int a, int b, int c, int d) {
  if (((1 << (c)) * (d)) == a && ((1 << (c)) * (d + 1)) == b) return w[c][d];
  c--, d = d * 2 + 1;
  if (b <= ((1 << (c)) * (d))) return f1(a, b, c, d - 1);
  if (a >= ((1 << (c)) * (d))) return f1(a, b, c, d);
  return f1(a, ((1 << (c)) * (d)), c, d - 1) + f1(((1 << (c)) * (d)), b, c, d);
}
void go(int a, int b) {
  if (a + 1 >= b) return;
  int mi = (a + b) / 2;
  go(a, mi);
  go(mi, b);
  ta = a, tb = mi, tc = a;
  while (tc != b) {
    if (tb == b || (ta != mi && v[ta] < v[tb])) {
      if (v[ta].second.first < 1000000007) {
        td = v[ta].second.first;
        for (int i = 0; i < 18; i++) {
          w[i][td] += v[ta].second.second;
          td /= 2;
        }
      }
      tv[tc++] = v[ta++];
    } else {
      if (v[tb].second.first >= 1000000007)
        ans[v[tb].second.first - 1000000007] +=
            f1(0, v[tb].second.second, 17, 0);
      tv[tc++] = v[tb++];
    }
  }
  for (int i = a; i < mi; i++)
    if (v[i].second.first < 1000000007) {
      td = v[i].second.first;
      for (int j = 0; j < 18; j++) {
        w[j][td] -= v[i].second.second;
        td /= 2;
      }
    }
  memcpy(v + a, tv + a, (b - a) * 12);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", x + i);
    if (!s[x[i]].empty())
      v[cnt++] =
          make_pair(-*s[x[i]].rbegin(), make_pair(i, i - *s[x[i]].rbegin()));
    s[x[i]].insert(s[x[i]].end(), i);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", q + i, &ta, &tb);
    ta--;
    if (q[i] == 1) {
      it = s[x[ta]].find(ta);
      if (it == s[x[ta]].begin())
        tc = -1;
      else {
        it--;
        tc = *it;
        it++;
        v[cnt++] = make_pair(-tc, make_pair(ta, tc - ta));
      }
      it++;
      if (it != s[x[ta]].end()) {
        v[cnt++] = make_pair(-ta, make_pair(*it, ta - *it));
        if (tc != -1) v[cnt++] = make_pair(-tc, make_pair(*it, *it - tc));
      }
      it--;
      s[x[ta]].erase(it);
      x[ta] = tb;
      it = s[tb].insert(ta).first;
      if (it == s[tb].begin())
        tc = -1;
      else {
        it--;
        tc = *it;
        it++;
        v[cnt++] = make_pair(-tc, make_pair(ta, ta - tc));
      }
      it++;
      if (it != s[tb].end()) {
        if (tc != -1) v[cnt++] = make_pair(-tc, make_pair(*it, tc - *it));
        v[cnt++] = make_pair(-ta, make_pair(*it, *it - ta));
      }
    } else
      v[cnt++] = make_pair(-ta, make_pair(1000000007 + i, tb));
  }
  go(0, cnt);
  for (int i = 0; i < m; i++)
    if (q[i] == 2) printf("%lld\n", ans[i]);
  return 0;
}
