#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
set<int> s[100050];
set<int>::iterator it;
long long sum[15000005];
int ls[15000005], rs[15000005];
int a[100050], rt[100050];
int n, m, tot;
void ins(int &x, int l, int r, int y, int v) {
  if (!x) x = ++tot;
  sum[x] += v;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (y <= mid)
    ins(ls[x], l, mid, y, v);
  else
    ins(rs[x], mid + 1, r, y, v);
}
long long find(int x, int l, int r, int y) {
  if (!x) return 0;
  if (l == r) return sum[x];
  int mid = (l + r) / 2;
  if (y <= mid)
    return find(ls[x], l, mid, y);
  else
    return sum[ls[x]] + find(rs[x], mid + 1, r, y);
}
void add(int x, int y, int v) {
  if (y > 0 && y <= n) {
    while (x <= n) ins(rt[x], 1, n, y, v), x += (x & (-x));
  }
}
long long getsum(int x, int y) {
  long long ans = 0;
  while (x) {
    ans += find(rt[x], 1, n, y);
    x -= (x & (-x));
  }
  return ans;
}
void add(int x1, int x2, int y1, int y2, int v) {
  if (x1 > x2 || y1 > y2) return;
  add(x1, y1, v);
  add(x2 + 1, y1, -v);
  add(x1, y2 + 1, -v);
  add(x2 + 1, y2 + 1, v);
}
void insert(int x, int y) {
  int l, r;
  it = s[x].lower_bound(y);
  r = (*it);
  it--;
  l = (*it);
  add(l + 1, y, r, n, r - y);
  add(1, l, y, r - 1, y - l);
  s[x].insert(y);
}
void del(int x, int y) {
  int l, r;
  it = s[x].upper_bound(y);
  r = (*it);
  it--;
  it--;
  l = (*it);
  add(l + 1, y, r, n, -(r - y));
  add(1, l, y, r - 1, -(y - l));
  s[x].erase(y);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) s[i].insert(0), s[i].insert(n + 1);
  for (int i = 1; i <= n; i++) a[i] = read(), insert(a[i], i);
  for (int i = 1; i <= m; i++) {
    int op = read(), x = read(), y = read();
    if (op == 1) {
      insert(y, x);
      del(a[x], x);
      a[x] = y;
    } else {
      printf("%d\n", getsum(x, y));
    }
  }
  return 0;
}
