#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1e5 + 55;
const int K = sqrt(MaxN);
const int INF = 1e9;
const int MOD = 1e9 + 7;
int n, m;
int a[MaxN];
int b[MaxN];
int WHAT[MaxN];
long long added[MaxN];
int type[MaxN];
int q[MaxN];
int w[MaxN];
int lastPos[MaxN];
long long sum[MaxN];
long long pref[MaxN];
long long suf[MaxN];
long long sumPref[MaxN];
long long sumSuf[MaxN];
set<int> s[MaxN];
vector<pair<int, int> > vector1;
vector<pair<pair<int, int>, int> > vector2;
void addElem(int pos, int x) {
  s[b[pos]].erase(pos);
  b[pos] = x;
  s[b[pos]].insert(pos);
}
void make() {
  memset(lastPos, 0, sizeof(lastPos));
  memset(sum, 0, sizeof(sum));
  memset(suf, 0, sizeof(suf));
  memset(pref, 0, sizeof(pref));
  for (int i = 1; i <= n; ++i) {
    s[i].clear();
    s[i].insert(0);
    s[i].insert(n + 1);
  }
  for (int i = 1; i <= n; ++i) {
    s[a[i]].insert(i);
    b[i] = a[i];
    pref[i] = 0;
    if (lastPos[a[i]]) {
      vector1.push_back(make_pair(lastPos[a[i]], i));
      pref[i] = i - lastPos[a[i]];
      sum[i] += pref[i];
    }
    lastPos[a[i]] = i;
  }
  memset(lastPos, 0, sizeof(lastPos));
  for (int i = n; i > 0; --i) {
    suf[i] = 0;
    if (lastPos[a[i]]) {
      suf[i] = lastPos[a[i]] - i;
      sum[i] += suf[i];
    }
    lastPos[a[i]] = i;
  }
  memset(lastPos, 0, sizeof(lastPos));
  long long cur = 0;
  for (int i = 1; i <= n; ++i) {
    if (lastPos[a[i]]) cur -= suf[lastPos[a[i]]];
    cur += suf[i];
    sumPref[i] = cur;
    lastPos[a[i]] = i;
  }
  memset(lastPos, 0, sizeof(lastPos));
  cur = 0;
  for (int i = n; i; --i) {
    if (lastPos[a[i]]) cur -= pref[lastPos[a[i]]];
    cur += pref[i];
    sumSuf[i] = cur;
    lastPos[a[i]] = i;
  }
  for (int i = 1; i <= n; ++i) sum[i] += sum[i - 1];
}
struct Tree {
  long long t[MaxN * 4];
  Tree() {
    for (int i = 0; i < MaxN * 4; ++i) t[i] = 0;
  }
  void clear() {
    for (int i = 0; i < MaxN * 4; ++i) t[i] = 0;
  }
  void up(int x, int l, int r, int pos, int delta) {
    t[x] += delta;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (mid >= pos)
      up(x + x, l, mid, pos, delta);
    else
      up(x + x + 1, mid + 1, r, pos, delta);
  }
  void up(int pos, int delta) { up(1, 1, MaxN - 1, pos, delta); }
  long long get(int x, int l, int r, int ll, int rr) {
    if (l > rr || r < ll) return 0;
    if (l >= ll && r <= rr) return t[x];
    int mid = (l + r) / 2;
    return get(x + x, l, mid, ll, rr) + get(x + x + 1, mid + 1, r, ll, rr);
  }
  long long get(int l, int r) { return get(1, 1, MaxN - 1, l, r); }
} tree;
struct pof {
  int pos, type, vType, number;
  pof() { pos = type = vType = number = 0; }
  pof(int pos, int type, int vType, int number)
      : pos(pos), type(type), vType(vType), number(number) {}
  bool operator<(const pof& oth) const {
    return (pos < oth.pos) || (pos == oth.pos && type < oth.type) ||
           (pos == oth.pos && type == oth.type && vType < oth.vType) ||
           (pos == oth.pos && type == oth.type && vType == oth.vType &&
            number < oth.number);
  }
};
void makeAll() {
  tree.clear();
  vector<pof> pofs;
  for (int i = 0; i < vector1.size(); ++i) {
    pofs.push_back(pof(vector1[i].first, 0, 0, vector1[i].second));
    pofs.push_back(pof(vector1[i].second, 1, 0, vector1[i].first));
  }
  for (int i = 0; i < vector2.size(); ++i) {
    pofs.push_back(pof(vector2[i].first.first, -2, vector2[i].first.second,
                       vector2[i].second));
  }
  sort(pofs.begin(), pofs.end());
  int l = 0;
  while (l < pofs.size()) {
    int r = l + 1;
    while (r < pofs.size() && pofs[l].pos == pofs[r].pos) ++r;
    for (int i = l; i < r; ++i)
      if (pofs[i].type == -2) {
        added[pofs[i].number] = tree.get(pofs[i].vType + 1, MaxN - 1);
      }
    for (int i = l; i < r; ++i)
      if (pofs[i].type == 0) {
        tree.up(pofs[i].number, pofs[i].number - pofs[i].pos);
      }
    l = r;
  }
}
void del(long long& ans, int pos, int l, int r) {
  if (pos < l || pos > r) return;
  int x = b[pos];
  set<int>::iterator it1 = s[x].lower_bound(pos);
  set<int>::iterator it2 = s[x].upper_bound(pos);
  --it1;
  int nPos = (*it2);
  int pPos = (*it1);
  if (nPos <= r && pPos >= l) return;
  if (nPos > r && pPos < l) return;
  if (nPos <= r) {
    ans -= nPos - pos;
  } else {
    ans -= pos - pPos;
  }
}
void add(long long& ans, int pos, int l, int r) {
  if (pos < l || pos > r) return;
  int x = b[pos];
  set<int>::iterator it1 = s[x].lower_bound(pos);
  set<int>::iterator it2 = s[x].upper_bound(pos);
  --it1;
  int nPos = (*it2);
  int pPos = (*it1);
  if (nPos <= r && pPos >= l) return;
  if (nPos > r && pPos < l) return;
  if (nPos <= r) {
    ans += nPos - pos;
  } else {
    ans += pos - pPos;
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= m; ++i) cin >> type[i] >> q[i] >> w[i];
  int l = 1;
  while (l <= m) {
    make();
    int r = min(m, l + K - 1);
    for (int i = l; i <= r; ++i)
      if (type[i] == 2) vector2.push_back(make_pair(make_pair(q[i], w[i]), i));
    makeAll();
    for (int i = l; i <= r; ++i) {
      if (type[i] == 2) {
        int L = q[i];
        int R = w[i];
        long long ans = sum[R] - sum[L - 1] - sumPref[L - 1] - sumSuf[R + 1] +
                        added[i] * 2ll;
        ans /= 2;
        for (int j = l; j < i; ++j)
          if (type[j] == 1) {
            WHAT[j] = b[q[j]];
            int curPos = q[j];
            int curX = w[j];
            del(ans, curPos, L, R);
            addElem(curPos, curX);
            add(ans, curPos, L, R);
          }
        cout << ans << '\n';
        for (int j = i - 1; j >= l; --j)
          if (type[j] == 1) {
            addElem(q[j], WHAT[j]);
          }
      }
    }
    for (int i = l; i <= r; ++i)
      if (type[i] == 1) a[q[i]] = w[i];
    l += K;
  }
  return 0;
}
