#include <bits/stdc++.h>
using namespace std;
int n, m, q[100005][3], z[100005], ii[100005], hv[100005], ta, tb, tc, td;
set<int> s[100005];
set<int>::iterator it, itt;
vector<pair<int, int> > x[100005], xx;
vector<int> v[18][100005], y[100005];
vector<vector<long long> > w[18][100005];
long long ans;
bool comp(int a, int b) {
  if (a >= 1000000007) a = hv[a - 1000000007];
  if (b >= 1000000007) b = hv[b - 1000000007];
  return xx[a] < xx[b];
}
void f1(int a, int b, int c, int d) {
  if (((1 << (c)) * (d)) == a && ((1 << (c)) * (d + 1)) == b) {
    tc = 1;
    for (int i = w[c][d].size() - 1; i >= 0 && tc; i--) {
      tc = min(tc, (int)w[c][d][i].size());
      td = v[c][d][((1 << (i)) * (tc - 1))];
      if (td >= 1000000007) td = hv[td - 1000000007];
      td = xx[td].first;
      if (td >= ta) {
        ans += w[c][d][i][tc - 1];
        tc--;
      }
      tc *= 2;
    }
    return;
  }
  c--, d = d * 2 + 1;
  if (b <= ((1 << (c)) * (d)))
    f1(a, b, c, d - 1);
  else if (a >= ((1 << (c)) * (d)))
    f1(a, b, c, d);
  else
    f1(a, ((1 << (c)) * (d)), c, d - 1), f1(((1 << (c)) * (d)), b, c, d);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", z + i);
    s[z[i]].insert(i);
  }
  for (int i = 1; i <= n; i++) {
    s[i].insert(-1);
    s[i].insert(n);
    for (it = s[i].begin(); it != s[i].end(); it++)
      if (*it != -1 && *it != n) {
        itt = it;
        itt--;
        x[*it].push_back(make_pair(*itt, *it - *itt));
      }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 3; j++) scanf("%d", q[i] + j);
    q[i][1]--;
    if (q[i][0] == 1 && z[q[i][1]] != q[i][2]) {
      it = s[z[q[i][1]]].find(q[i][1]);
      itt = it;
      itt--;
      ta = *itt;
      itt = it;
      itt++;
      tb = *itt;
      if (tb != n) {
        y[i].push_back(tb);
        x[tb].push_back(make_pair(ta, tb - ta));
      }
      s[z[q[i][1]]].erase(it);
      it = s[z[q[i][1]] = q[i][2]].insert(q[i][1]).first;
      itt = it;
      itt--;
      ta = *itt;
      itt = it;
      itt++;
      tb = *itt;
      if (tb != n) {
        y[i].push_back(tb);
        x[tb].push_back(make_pair(q[i][1], tb - q[i][1]));
      }
      y[i].push_back(q[i][1]);
      x[q[i][1]].push_back(make_pair(ta, q[i][1] - ta));
    }
  }
  for (int i = 1; i <= n; i++) s[i].clear();
  for (int i = 0; i < n; i++) {
    hv[i + 1] = hv[i] + x[i].size();
    for (int k = 0; k < x[i].size(); k++) xx.push_back(x[i][k]);
  }
  for (int i = 0; i < n; i++) {
    ta = i;
    for (int j = 0; j < 18; j++) {
      for (int l = 0; l < x[i].size(); l++)
        if (((1 << (j)) * (ta + 1)) <= n)
          v[j][ta].push_back(l ? hv[i] + l : 1000000007 + i);
      ta /= 2;
    }
  }
  for (int i = 0; i < 18; i++)
    for (int j = 0; ((1 << (i)) * (j + 1)) <= n; j++) {
      sort(v[i][j].begin(), v[i][j].end(), comp);
      w[i][j].push_back(vector<long long>(v[i][j].size(), 0LL));
      for (int l = 0; l < v[i][j].size(); l++)
        if (v[i][j][l] >= 1000000007)
          w[i][j][0][l] = x[v[i][j][l] - 1000000007][0].second;
      while (w[i][j].back().size() > 1) {
        ta = w[i][j].size() - 1;
        tb = w[i][j].back().size();
        w[i][j].push_back(vector<long long>((tb + 1) / 2, 0LL));
        for (int l = 0; l < tb; l += 2) {
          if (l + 1 < tb)
            w[i][j].back()[l / 2] = w[i][j][ta][l] + w[i][j][ta][l + 1];
          else
            w[i][j].back()[l / 2] = w[i][j][ta][l];
        }
      }
    }
  for (int i = 0; i < m; i++)
    if (q[i][0] == 1) {
      if (!y[i].empty())
        for (int p = 0; p < y[i].size(); p++) {
          ta = y[i][p];
          int l = ta;
          for (int k = 0; k < 18; k++) {
            if (((1 << (k)) * (l + 1)) <= n) {
              tb = lower_bound(v[k][l].begin(), v[k][l].end(),
                               ii[ta] ? hv[ta] + ii[ta] : 1000000007 + ta,
                               comp) -
                   v[k][l].begin();
              for (int r = 0; r < w[k][l].size(); r++) {
                w[k][l][r][tb] -= x[ta][ii[ta]].second;
                tb /= 2;
              }
            }
            l /= 2;
          }
          ii[ta]++;
          l = ta;
          for (int k = 0; k < 18; k++) {
            if (((1 << (k)) * (l + 1)) <= n) {
              tb = lower_bound(v[k][l].begin(), v[k][l].end(),
                               ii[ta] ? hv[ta] + ii[ta] : 1000000007 + ta,
                               comp) -
                   v[k][l].begin();
              for (int r = 0; r < w[k][l].size(); r++) {
                w[k][l][r][tb] += x[ta][ii[ta]].second;
                tb /= 2;
              }
            }
            l /= 2;
          }
        }
    } else {
      ans = 0;
      f1(ta = q[i][1], tb = q[i][2], 17, 0);
      printf("%lld\n", ans);
    }
  return 0;
}
