#include <bits/stdc++.h>
using namespace std;
namespace Input {
const int BUF = 65536;
char buf[BUF + 1];
char *head = buf, *tail = buf;
inline char inputchar() {
  if (head == tail) *(tail = (head = buf) + fread(buf, 1, BUF, stdin)) = 0;
  return *head++;
}
inline void inputnum(int &ret) {
  char ch = inputchar();
  while (ch < '0' || ch > '9') ch = inputchar();
  for (ret = 0; ch >= '0' && ch <= '9'; ch = inputchar())
    ret = ret * 10 + ch - '0';
}
};  // namespace Input
using Input::inputnum;
const int MAXN = 100005;
struct Node {
  long long sum;
  Node *c[2];
  Node() {}
  Node(Node *a, Node *b) : sum(0) { c[0] = a, c[1] = b; }
  inline void modify(int v) { sum = v; }
  inline void update() {
    sum = (c[0] ? c[0]->sum : 0) + (c[1] ? c[1]->sum : 0);
  }
} node[MAXN * 90], *root[MAXN];
int cnt = 0;
inline Node *newnode() {
  node[cnt] = Node(0, 0);
  return &node[cnt++];
}
void modify(Node *&p, int x, int L, int R, int v) {
  if (!p) p = newnode();
  if (L == R) {
    p->modify(v);
    return;
  }
  int M = (L + R) >> 1;
  if (x <= M)
    modify(p->c[0], x, L, M, v);
  else
    modify(p->c[1], x, M + 1, R, v);
  p->update();
}
long long query(Node *p, int qL, int qR, int L, int R) {
  if (!p) return 0;
  if (L >= qL && R <= qR) return p->sum;
  int M = (L + R) >> 1;
  long long ret = 0;
  if (qL <= M) ret += query(p->c[0], qL, qR, L, M);
  if (qR > M) ret += query(p->c[1], qL, qR, M + 1, R);
  return ret;
}
set<int> pos[MAXN];
int a[MAXN];
int n, m, id, p, y, l, r;
inline void modify(int x, int y, int v) {
  for (int i = x; i <= n; i += (i & -i)) modify(root[i], y, 1, n, v);
}
inline long long query(int x, int R) {
  long long ret = 0;
  for (int i = x; i > 0; i ^= (i & -i)) ret += query(root[i], 1, R, 1, n);
  return ret;
}
void init() {
  memset(root, 0, sizeof(root));
  for (int i = 1; i <= n; i++) {
    set<int> &cur = pos[a[i]];
    cur.insert(i);
    set<int>::iterator pre = cur.find(i);
    if (pre != cur.begin()) {
      --pre;
      modify(*pre, i, i - *pre);
    }
  }
}
int main() {
  inputnum(n), inputnum(m);
  for (int i = 1; i <= n; i++) inputnum(a[i]);
  init();
  for (int i = 1; i <= m; i++) {
    inputnum(id);
    if (id == 1) {
      inputnum(p), inputnum(y);
      int x = a[p];
      a[p] = y;
      set<int> &sx = pos[x], &sy = pos[y];
      set<int>::iterator pre, next;
      pre = next = sx.find(p);
      ++next;
      if (pre != sx.begin() && next != sx.end()) {
        --pre;
        modify(*pre, p, 0);
        modify(p, *next, 0);
        modify(*pre, *next, *next - *pre);
      } else if (pre != sx.begin()) {
        --pre;
        modify(*pre, p, 0);
      } else if (next != sx.end()) {
        modify(p, *next, 0);
      }
      sx.erase(p);
      sy.insert(p);
      pre = next = sy.find(p);
      ++next;
      if (pre != sy.begin() && next != sy.end()) {
        --pre;
        modify(*pre, *next, 0);
        modify(*pre, p, p - *pre);
        modify(p, *next, *next - p);
      } else if (pre != sy.begin()) {
        --pre;
        modify(*pre, p, p - *pre);
      } else if (next != sy.end()) {
        modify(p, *next, *next - p);
      }
    } else {
      inputnum(l), inputnum(r);
      printf("%I64d\n", query(r, r) - query(l - 1, r));
    }
  }
  return 0;
}
