#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 2, sqr = 317, NONE = -1;
int n, q, val[N], qt[N], ql[N], qr[N], prv[N], sortedprv[N];
set<int> pos[N];
long long sum[N];
inline int bucket(int i) { return i / sqr; }
void recalcbucket(int where) {
  int bg = where * sqr, ed = min(n - 1, (where + 1) * sqr - 1);
  vector<pair<int, int>> consec;
  for (int i = bg; i <= ed; ++i) {
    consec.emplace_back(prv[i], i);
  }
  sort(consec.begin(), consec.end());
  reverse(begin(consec), end(consec));
  for (int i = bg; i <= ed; ++i) {
    if (i != bg) {
      sum[i] = sum[i - 1];
    } else {
      sum[i] = 0;
    }
    if (consec[i - bg].first != NONE) {
      sum[i] += consec[i - bg].second - consec[i - bg].first;
    }
    sortedprv[i] = consec[i - bg].first;
  }
}
void update(int i, int x) {
  if (val[i] == x) {
    return;
  }
  auto it = pos[val[i]].upper_bound(i);
  if (it != end(pos[val[i]])) {
    prv[*it] = prv[i];
    recalcbucket(bucket(*it));
  }
  pos[val[i]].erase(i);
  auto firstbigger = pos[x].upper_bound(i);
  auto firstsmaller = pos[x].upper_bound(i);
  if (firstsmaller != begin(pos[x])) {
    firstsmaller--;
    prv[i] = *firstsmaller;
    recalcbucket(bucket(*firstsmaller));
  } else
    prv[i] = NONE;
  if (firstbigger != end(pos[x])) {
    prv[*firstbigger] = i;
    recalcbucket(bucket(*firstbigger));
  }
  val[i] = x, recalcbucket(bucket(i));
  pos[x].insert(i);
}
long long bucketQuery(int where, int i) {
  int bg = where * sqr, ed = min(n - 1, (where + 1) * sqr - 1);
  int st = bg, dr = ed, ans = -1;
  while (st <= dr) {
    int mij = (st + dr) >> 1;
    if (sortedprv[mij] >= i) {
      st = mij + 1;
      ans = mij;
    } else
      dr = mij - 1;
  }
  if (ans == -1) return 0;
  return sum[ans];
}
long long query(int i, int j) {
  int k = i;
  long long ret = 0;
  while (k <= j && k % sqr) {
    if (prv[k] != NONE && prv[k] >= i) {
      ret += k - prv[k];
    }
    ++k;
  }
  while (k + sqr - 1 <= j) {
    int currBucket = bucket(k);
    ret += bucketQuery(currBucket, i);
    k += sqr;
  }
  while (k <= j) {
    if (prv[k] != NONE && prv[k] >= i) {
      ret += k - prv[k];
    }
    ++k;
  }
  return ret;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; ++i) {
    scanf("%d", val + i);
    pos[val[i]].insert(i);
  }
  for (int i = 0; i < n; ++i) {
    auto it = pos[val[i]].lower_bound(i);
    if (it != begin(pos[val[i]])) {
      --it;
      prv[i] = *it;
    } else
      prv[i] = NONE;
  }
  for (int i = 0; i < n; i += sqr) recalcbucket(bucket(i));
  for (int i = 0; i < q; ++i) {
    scanf("%d %d %d", &qt[i], &ql[i], &qr[i]);
    if (qt[i] == 1) {
      ql[i]--;
    } else {
      --ql[i];
      --qr[i];
    }
  }
  for (int i = 0; i < q; ++i) {
    if (qt[i] == 1) {
      update(ql[i], qr[i]);
    } else {
      printf("%I64d\n", query(ql[i], qr[i]));
    }
  }
  return 0;
}
