#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
const int SQ = 350;
int arr[MAX];
int nxt[MAX];
int pre[MAX];
int lst[MAX];
int block[MAX];
int l[(MAX / SQ) + 5];
int r[(MAX / SQ) + 5];
int bit1[(MAX / SQ) + 5][MAX];
int bit2[(MAX / SQ) + 5][MAX];
int cur;
set<pair<int, int> > s;
int n;
void upd1(int x, int y, int val) {
  y++;
  while (y <= n) {
    bit1[x][y] += val;
    y += (y & (-y));
  }
}
void upd2(int x, int y, int val) {
  y--;
  while (y) {
    bit2[x][y] += val;
    y -= (y & (-y));
  }
}
long long query1(int x, int y) {
  long long ans = 0;
  while (y) {
    ans += bit1[x][y];
    y -= (y & (-y));
  }
}
long long query2(int x, int y) {
  long long ans = 0;
  while (y <= n) {
    ans += bit2[x][y];
    y += (y & (-y));
  }
}
long long query(int st, int en) {
  long long res = 0;
  for (int i = block[st]; i <= block[en]; i++) {
    if (l[i] >= st && r[i] <= en) {
      res += query2(i, en);
      res -= query1(i, st);
    } else {
      for (int j = max(st, l[i]); j <= min(en, r[i]); j++) {
        if (pre[j] < st) {
          res -= j;
        }
        if (nxt[j] > en) {
          res += j;
        }
      }
    }
  }
  return res;
}
void update(int idx, int val) {
  int old = arr[idx];
  if (old == val) {
    return;
  }
  if (pre[idx] != 0) {
    upd2(block[pre[idx]], nxt[pre[idx]], -pre[idx]);
    upd2(block[pre[idx]], nxt[idx], pre[idx]);
    nxt[pre[idx]] = nxt[idx];
  }
  if (nxt[idx] != (n + 1)) {
    upd1(block[nxt[idx]], pre[nxt[idx]], -nxt[idx]);
    upd1(block[nxt[idx]], pre[idx], nxt[idx]);
    pre[nxt[idx]] = pre[idx];
  }
  upd1(block[idx], pre[idx], -idx);
  upd2(block[idx], nxt[idx], -idx);
  s.erase(make_pair(old, idx));
  arr[idx] = val;
  s.insert(make_pair(val, idx));
}
int main() {
  int m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    s.insert(make_pair(arr[i], i));
  }
  for (int i = 1; i <= n; i++) {
    pre[i] = lst[arr[i]];
    lst[arr[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    lst[arr[i]] = n + 1;
  }
  for (int i = n; i >= 1; i--) {
    nxt[i] = lst[arr[i]];
    lst[arr[i]] = i;
  }
  for (int i = 1; i <= n; i += SQ) {
    ++cur;
    l[cur] = i;
    r[cur] = min(n, i + SQ - 1);
    for (int j = l[cur]; j <= r[cur]; j++) {
      block[j] = cur;
    }
  }
  for (int i = 1; i <= n; i++) {
    upd1(block[i], pre[i], i);
    upd2(block[i], nxt[i], i);
  }
  for (int i = 1; i <= m; i++) {
    int typ;
    scanf("%d", &typ);
    if (typ == 2) {
      int x, y;
      scanf("%d %d", &x, &y);
      printf("%lld\n", query(x, y));
    }
    if (typ == 1) {
      int x, y;
      scanf("%d %d", &x, &y);
      update(x, y);
    }
  }
  return 0;
}
