#include <bits/stdc++.h>
using namespace std;
int n, m;
const int max_n = 1e5;
const int sn = 317;
int a[max_n];
int bi[max_n];
set<int> pos[max_n];
struct Node {
  long long int sum;
  Node *l, *r;
  Node() {
    sum = 0;
    l = NULL;
    r = NULL;
  }
  void up() {
    sum = 0;
    if (l != NULL) sum += l->sum;
    if (r != NULL) sum += r->sum;
  }
};
struct Tree {
  Node* root = new Node();

 private:
  void update(Node*& node, int l, int r, int pos, int val) {
    if (node == NULL) node = new Node();
    if (l == r) {
      node->sum += val;
    } else {
      int mid = (l + r) >> 1;
      if (pos <= mid)
        update(node->l, l, mid, pos, val);
      else
        update(node->r, mid + 1, r, pos, val);
      node->up();
    }
  }
  long long int query(Node* node, int l, int r, int a, int b) {
    if (node == NULL) return 0;
    if (l == a && r == b) return node->sum;
    int mid = (l + r) >> 1;
    if (b <= mid)
      return query(node->l, l, mid, a, b);
    else if (a >= mid + 1)
      return query(node->r, mid + 1, r, a, b);
    else
      return query(node->l, l, mid, a, mid) +
             query(node->r, mid + 1, r, mid + 1, b);
  }

 public:
  long long int query(int y) { return query(root, 0, n, 0, y); }
  void update(int y, int val) { update(root, 0, n, y, val); }
} trees[sn + 1];
void change(int i, int to) {
  auto it = pos[a[i]].find(i);
  auto it2 = it;
  int my_prev = (it == pos[a[i]].begin()) ? *it : *(--it);
  int my_next = (++it2 == pos[a[i]].end()) ? i : *it2;
  if (my_prev != i) {
    trees[bi[my_prev]].update(i, my_prev - i);
    if (my_next != i) {
      trees[bi[my_prev]].update(my_next, my_next - my_prev);
    }
  }
  if (my_next != i) {
    trees[bi[i]].update(my_next, i - my_next);
  }
  pos[a[i]].erase(i);
  pos[to].insert(i);
  it = pos[to].find(i);
  it2 = it;
  my_prev = (it == pos[to].begin()) ? *it : *(--it);
  my_next = (++it2 == pos[to].end()) ? i : *it2;
  trees[bi[i]].update(my_next, my_next - i);
  if (my_prev != i) {
    if (my_next != i) {
      trees[bi[my_prev]].update(my_next, my_prev - my_next);
    }
    trees[bi[my_prev]].update(i, i - my_prev);
  }
  a[i] = to;
}
long long int query(int s, int e, int y) {
  e = min(e, n - 1);
  long long int res = 0;
  for (int i = s; i <= e; ++i) {
    auto it = pos[a[i]].find(i);
    int my_next = (++it == pos[a[i]].end()) ? i : *it;
    if (my_next <= y) {
      res += my_next - i;
    }
  }
  return res;
}
long long int ask(int a, int b) {
  int y = b;
  int start = bi[a];
  int end = bi[b];
  long long int res = 0;
  for (int i = start + 1; i <= end - 1; ++i) {
    res += trees[i].query(y);
  }
  res += query(a, min(b, sn * (start + 1) - 1), y);
  if (sn * end > a) {
    res += query(sn * end, b, y);
  }
  return res;
}
void init() {
  int my_buc = 0;
  int c = -1;
  for (int i = 0; i < n; ++i) {
    c++;
    if (c == sn) {
      c = 0;
      my_buc++;
    }
    bi[i] = my_buc;
  }
  for (int i = 0; i < n; ++i) {
    pos[a[i]].insert(i);
  }
  for (int i = 0; i < n; ++i) {
    auto it = pos[a[i]].find(i);
    int my_prev = (it == pos[a[i]].begin()) ? *it : *(--it);
    trees[bi[my_prev]].update(i, i - my_prev);
  }
}
void write() {}
void read() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
  }
  init();
  while (m) {
    int op, b, c;
    cin >> op >> b >> c;
    b--;
    c--;
    if (op == 1) {
      change(b, c);
    } else {
      cout << ask(b, c) << endl;
    }
    m--;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  read();
  return 0;
}
