#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;
const double PI = acos(-1.0);
const int oo = 0x3f3f3f3f;
const int P = 998244353;
const int PR = 3;
long long read() {
  long long d, f = 1;
  char c;
  while (!isdigit(c = getchar()))
    if (c == '-') f = -1;
  d = c ^ '0';
  while (isdigit(c = getchar())) d = (d * 10) + (c ^ '0');
  return d * f;
}
const int N = 1e5 + 5;
int a[N], belong[N];
int last[N], nxt[N];
long long ans[N];
struct node {
  int l, r, k, ord;
  long long ans;
  node(int _l, int _r, int _k, int _ord) : l(_l), r(_r), k(_k), ord(_ord) {
    ans = 0;
  }
};
vector<node> q;
vector<pair<int, int> > upd, rupd;
set<int> pos[N];
bool cmp1(node x, node y) {
  return belong[x.l] == belong[y.l] ? belong[x.r] == belong[y.r]
                                          ? x.k < y.k
                                          : belong[x.r] < belong[y.r]
                                    : belong[x.l] < belong[y.l];
}
bool cmp2(node x, node y) { return x.ord < y.ord; }
int main() {
  int n, m;
  while (cin >> n >> m) {
    int block_size = ceil(pow(n, 2.0 / 3));
    for (int i = (1); i <= (n); ++i) {
      scanf("%d", &a[i]);
      pos[a[i]].insert(i);
      last[i] = -oo, nxt[i] = oo;
      belong[i] = (i - 1) / block_size;
    }
    for (int i = (1); i <= (n); ++i)
      if (!pos[i].empty()) {
        auto j = pos[i].begin(), k = j;
        for (++k; k != pos[i].end(); j = k, ++k) last[*k] = *j, nxt[*j] = *k;
      }
    q.emplace_back(1, 1, 0, 0);
    upd.emplace_back(0, 0);
    for (int i = (1); i <= (m); ++i) {
      int type, a, b;
      scanf("%d%d%d", &type, &a, &b);
      if (type == 1)
        upd.emplace_back(a, b);
      else
        q.emplace_back(a, b, upd.size() - 1, i);
    }
    sort(q.begin(), q.end(), cmp1);
    for (auto i : upd) {
      rupd.emplace_back(i.first, a[i.first]);
      a[i.first] = i.second;
    }
    for (auto i : rupd) a[i.first] = i.second;
    auto i = q.begin();
    for (auto j = q.begin() + 1; j != q.end(); i = j, ++j) {
      j->ans = i->ans;
      if (j->l < i->l) {
        for (int p = (i->l - 1); p >= (j->l); --p)
          if (nxt[p] <= i->r) j->ans += nxt[p] - p;
        if (j->r < i->r) {
          for (int p = (i->r); p >= (j->r + 1); --p)
            if (last[p] >= j->l) j->ans -= p - last[p];
        } else {
          for (int p = (i->r + 1); p <= (j->r); ++p)
            if (last[p] >= j->l) j->ans += p - last[p];
        }
      } else {
        if (j->r < i->r) {
          for (int p = (i->r); p >= (j->r + 1); --p)
            if (last[p] >= i->l) j->ans -= p - last[p];
        } else {
          for (int p = (i->r + 1); p <= (j->r); ++p)
            if (last[p] >= i->l) j->ans += p - last[p];
        }
        for (int p = (i->l); p <= (j->l - 1); ++p)
          if (nxt[p] <= j->r) j->ans -= nxt[p] - p;
      }
      if (j->k < i->k) {
        for (int p = (i->k); p >= (j->k + 1); --p) {
          bool flag = j->l <= rupd[p].first && rupd[p].first <= j->r;
          if (last[rupd[p].first] != -oo)
            nxt[last[rupd[p].first]] = nxt[rupd[p].first];
          else if (flag && nxt[rupd[p].first] <= j->r)
            j->ans -= nxt[rupd[p].first] - rupd[p].first;
          if (nxt[rupd[p].first] != oo)
            last[nxt[rupd[p].first]] = last[rupd[p].first];
          else if (flag && last[rupd[p].first] >= j->l)
            j->ans -= rupd[p].first - last[rupd[p].first];
          pos[a[rupd[p].first]].erase(rupd[p].first);
          a[rupd[p].first] = rupd[p].second;
          last[rupd[p].first] = -oo, nxt[rupd[p].first] = oo;
          pos[a[rupd[p].first]].insert(rupd[p].first);
          auto it2 = pos[a[rupd[p].first]].find(rupd[p].first);
          if (it2 != pos[a[rupd[p].first]].begin()) {
            auto it1 = it2;
            --it1;
            nxt[*it1] = *it2;
            last[*it2] = *it1;
          }
          if (*it2 != *pos[a[rupd[p].first]].rbegin()) {
            auto it3 = it2;
            ++it3;
            last[*it3] = *it2;
            nxt[*it2] = *it3;
          }
          if (flag) {
            if (last[*it2] == -oo && nxt[*it2] <= j->r)
              j->ans += nxt[*it2] - *it2;
            if (nxt[*it2] == oo && last[*it2] >= j->l)
              j->ans += *it2 - last[*it2];
          }
        }
      } else {
        for (int p = (i->k + 1); p <= (j->k); ++p) {
          bool flag = j->l <= upd[p].first && upd[p].first <= j->r;
          if (last[upd[p].first] != -oo)
            nxt[last[upd[p].first]] = nxt[upd[p].first];
          else if (flag && nxt[upd[p].first] <= j->r)
            j->ans -= nxt[upd[p].first] - upd[p].first;
          if (nxt[upd[p].first] != oo)
            last[nxt[upd[p].first]] = last[upd[p].first];
          else if (flag && last[upd[p].first] >= j->l)
            j->ans -= upd[p].first - last[upd[p].first];
          pos[a[upd[p].first]].erase(upd[p].first);
          a[upd[p].first] = upd[p].second;
          last[upd[p].first] = -oo, nxt[upd[p].first] = oo;
          pos[a[upd[p].first]].insert(upd[p].first);
          auto it2 = pos[a[upd[p].first]].find(upd[p].first);
          if (it2 != pos[a[upd[p].first]].begin()) {
            auto it1 = it2;
            --it1;
            nxt[*it1] = *it2;
            last[*it2] = *it1;
          }
          if (*it2 != *pos[a[upd[p].first]].rbegin()) {
            auto it3 = it2;
            ++it3;
            last[*it3] = *it2;
            nxt[*it2] = *it3;
          }
          if (flag) {
            if (last[*it2] == -oo && nxt[*it2] <= j->r)
              j->ans += nxt[*it2] - *it2;
            if (nxt[*it2] == oo && last[*it2] >= j->l)
              j->ans += *it2 - last[*it2];
          }
        }
      }
    }
    sort(q.begin(), q.end(), cmp2);
    for (auto i = q.begin() + 1; i != q.end(); ++i) printf("%lld\n", i->ans);
  }
  return 0;
}
