#include <bits/stdc++.h>
using namespace std;
set<int> onIds[(1 << 20)];
struct vs {
  int l, r, ind, pr;
  long long sum, x;
  vs() {
    x = -1;
    ind = -1;
    pr = rand() * rand() + rand();
    l = 0;
    r = 0;
    sum = 0;
  }
} roots[(1 << 21)];
int rootIds[(1 << 20)];
vector<int> emptyIds;
int n, q, k = 18, lastAv = 1;
int mergeV(int l, int r) {
  if (l == 0) {
    return r;
  }
  if (r == 0) {
    return l;
  }
  if (roots[l].pr > roots[r].pr) {
    int c = mergeV(roots[l].r, r);
    roots[l].r = c;
    roots[l].sum = roots[l].x + roots[roots[l].l].sum + roots[roots[l].r].sum;
    return l;
  } else {
    int c = mergeV(l, roots[r].l);
    roots[r].l = c;
    roots[r].sum = roots[r].x + roots[roots[r].l].sum + roots[roots[r].r].sum;
    return r;
  }
}
pair<int, int> splitV(int l, int k) {
  if (l == 0) {
    return make_pair(0, 0);
  }
  if (roots[l].ind <= k) {
    pair<int, int> c = splitV(roots[l].r, k);
    roots[l].r = c.first;
    roots[l].sum = roots[l].x + roots[roots[l].l].sum + roots[roots[l].r].sum;
    return make_pair(l, c.second);
  } else {
    pair<int, int> c = splitV(roots[l].l, k);
    roots[l].l = c.second;
    roots[l].sum = roots[l].x + roots[roots[l].l].sum + roots[roots[l].r].sum;
    return make_pair(c.first, l);
  }
}
void addInd(int ll, int rr, int x, int val, int crr) {
  if (val > 0) {
    int itInd = crr;
    crr = rootIds[crr];
    pair<int, int> c = splitV(crr, x);
    roots[emptyIds.back()].x = val;
    roots[emptyIds.back()].ind = x;
    roots[emptyIds.back()].sum = val;
    int iii = emptyIds.back();
    emptyIds.pop_back();
    crr = mergeV(c.first, iii);
    crr = mergeV(crr, c.second);
    rootIds[itInd] = crr;
  } else {
    int itInd = crr;
    crr = rootIds[crr];
    pair<int, int> c = splitV(crr, x - 1);
    pair<int, int> cr = splitV(c.second, x);
    roots[cr.first] = vs();
    emptyIds.push_back(cr.first);
    crr = mergeV(c.first, cr.second);
    rootIds[itInd] = crr;
  }
}
void addElement(int lPos, int rPos, int val) {
  int ind = rPos + (1 << k);
  for (; ind; ind /= 2) {
    addInd(0, (1 << k), lPos, val, ind);
  }
}
long long getSum(int l, int r, int ll, int rr, int crr) {
  int itInd = crr;
  crr = rootIds[crr];
  pair<int, int> c = splitV(crr, l - 1);
  long long ans = roots[c.second].sum;
  crr = mergeV(c.first, c.second);
  rootIds[itInd] = crr;
  return ans;
}
long long getRoot(int l, int r, int ll = 0, int rr = (1 << k), int ind = 1) {
  if (l <= ll && rr <= r) {
    return getSum(l, r, 0, (1 << k), ind);
  }
  if (rr <= l || r <= ll) {
    return 0;
  }
  return getRoot(l, r, ll, (ll + rr) / 2, ind * 2) +
         getRoot(l, r, (ll + rr) / 2, rr, ind * 2 + 1);
}
int arr[(1 << 20)];
void rem(int t, int i) {
  auto rit = onIds[t].upper_bound(i);
  auto lit = onIds[t].lower_bound(i);
  int l = -1, r = -1;
  if (rit != onIds[t].end()) {
    r = *rit;
  }
  if (lit != onIds[t].begin()) {
    lit--;
    l = *lit;
  }
  if (l != -1) {
    addElement(l, i, -(i - l));
  }
  if (r != -1) {
    addElement(i, r, -(r - i));
  }
  if (l != -1 && r != -1) {
    addElement(l, r, (r - l));
  }
  onIds[t].erase(i);
}
void add(int t, int i) {
  auto rit = onIds[t].upper_bound(i);
  auto lit = onIds[t].upper_bound(i);
  int l = -1, r = -1;
  if (rit != onIds[t].end()) {
    r = *rit;
  }
  if (lit != onIds[t].begin()) {
    lit--;
    l = *lit;
  }
  if (l != -1 && r != -1) {
    addElement(l, r, -(r - l));
  }
  if (l != -1) {
    addElement(l, i, i - l);
  }
  if (r != -1) {
    addElement(i, r, r - i);
  }
  onIds[t].insert(i);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  srand(42);
  for (int i = 1; i < (1 << 21); i++) {
    emptyIds.push_back(i);
  }
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    if (onIds[arr[i]].size()) {
      auto lPos = onIds[arr[i]].end();
      lPos--;
      addElement(*lPos, i, i - (*lPos));
    }
    onIds[arr[i]].insert(i);
  }
  for (int i = 0; i < q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 1) {
      int ind = l - 1, newT = r;
      rem(arr[ind], ind);
      add(newT, ind);
      arr[ind] = newT;
    } else {
      l--;
      cout << getRoot(l, r) << "\n";
    }
  }
  return 0;
}
