#include <bits/stdc++.h>
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  char ch;
  while (blank(ch = nc()))
    ;
  if (IOerror) return;
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
}
};  // namespace fastIO
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline bool scan(T &ret) {
  char c;
  int sgn;
  if (c = getchar(), c == EOF) return 0;
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
  ret *= sgn;
  return 1;
}
const double pi = 3.14159265358979323846264338327950288L;
using namespace std;
int n, m, val[100005], pos[100005];
set<int> s[100005];
struct BIT {
  map<int, long long> c[100005];
  void insert(int l, int r, int val) {
    for (int i = l; i >= 1; i -= lowbit(i)) {
      for (int j = r; j <= n; j += lowbit(j)) {
        c[i][j] += val;
      }
    }
  }
  long long query(int l, int r) {
    if (l <= 0 || r <= 0) return 0;
    long long ans = 0;
    for (int i = l; i <= n; i += lowbit(i)) {
      for (int j = r; j >= 1; j -= lowbit(j)) {
        ans += c[i][j];
      }
    }
    return ans;
  }
} bit;
void update(int pos, int v) {
  int tmp = val[pos];
  set<int>::iterator it1, it2;
  it1 = it2 = s[tmp].upper_bound(pos);
  it1--;
  if (it2 != s[tmp].end()) bit.insert(pos, (*it2), pos - (*it2));
  if (it1 != s[tmp].begin()) {
    it1--;
    bit.insert((*it1), pos, (*it1) - pos);
    if (it2 != s[tmp].end()) bit.insert((*it1), (*it2), (*it2) - (*it1));
  }
  s[tmp].erase(pos);
  it1 = it2 = s[v].upper_bound(pos);
  if (it2 != s[v].end()) bit.insert(pos, (*it2), (*it2) - pos);
  if (it1 != s[v].begin()) {
    it1--;
    bit.insert((*it1), pos, pos - (*it1));
    if (it2 != s[v].end()) bit.insert((*it1), (*it2), (*it1) - (*it2));
  }
  s[v].insert(pos);
  val[pos] = v;
}
void solve() {
  for (int i = 0; i < m; i++) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      if (r != val[l]) update(l, r);
    } else {
      long long ans = bit.query(l, r);
      printf("%lld\n", ans);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  memset(pos, 0, sizeof(pos));
  for (int i = 1; i <= n; i++) {
    s[i].clear();
    bit.c[i].clear();
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &val[i]);
    if (pos[val[i]]) bit.insert(pos[val[i]], i, i - pos[val[i]]);
    pos[val[i]] = i;
    s[val[i]].insert(i);
  }
  solve();
  return 0;
}
