#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch - '0' < 0 || ch - '0' > 9) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch - '0' >= 0 && ch - '0' <= 9) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m;
set<int> s[100010];
int val[100010];
struct P {
  int x, y, t, id, val;
} a[100010 * 9], tmp1[100010 * 9], tmp2[100010 * 9];
int top1, top2;
bool cmp(P a, P b) {
  if (a.t != b.t) return a.t < b.t;
  if (a.y != b.y) return a.y < b.y;
  if (a.x != b.x) return a.x > b.x;
}
int top;
void add(int id, int x, int tim) {
  s[id].insert(x);
  set<int>::iterator it = s[id].lower_bound(x), it2 = it;
  int L = 0, R = 0;
  it2++;
  if (it2 != s[id].end()) R = (*s[id].upper_bound(x));
  if (it != s[id].begin()) {
    --it;
    L = (*it);
  }
  if (L) a[++top] = (P){L, x, tim, 0, x - L};
  if (R) a[++top] = (P){x, R, tim, 0, R - x};
  if (L && R) a[++top] = (P){L, R, tim, 0, L - R};
}
void del(int id, int x, int tim) {
  set<int>::iterator it = s[id].lower_bound(x), it2 = it;
  int L = 0, R = 0;
  it2++;
  if (it2 != s[id].end()) R = (*s[id].upper_bound(x));
  if (it != s[id].begin()) {
    --it;
    L = (*it);
  }
  if (L) a[++top] = (P){L, x, tim, 0, L - x};
  if (R) a[++top] = (P){x, R, tim, 0, x - R};
  if (L && R) a[++top] = (P){L, R, tim, 0, R - L};
  it = s[id].lower_bound(x);
  s[id].erase(it);
}
long long ans[100010];
struct BIT {
  long long t[100010];
  int lowbit(int x) { return x & (-x); }
  void modi(int x, int y) {
    for (int i = x; i <= n; i += lowbit(i)) t[i] += y;
  }
  long long query(int x) {
    long long res = 0;
    for (int i = x; i; i -= lowbit(i)) res += t[i];
    return res;
  }
} B;
int cnt;
void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  solve(l, mid);
  solve(mid + 1, r);
  top1 = top2 = 0;
  for (int i = l; i <= mid; i++) tmp1[++top1] = a[i];
  for (int i = mid + 1; i <= r; i++) tmp2[++top2] = a[i];
  int pos1 = 1, pos2 = 1;
  int pos = l;
  while (pos1 <= top1 && pos2 <= top2) {
    if (tmp1[pos1].y <= tmp2[pos2].y) {
      if (!tmp1[pos1].id) B.modi(tmp1[pos1].x, tmp1[pos1].val);
      a[pos++] = tmp1[pos1];
      ++pos1;
    } else {
      if (tmp2[pos2].id)
        ans[tmp2[pos2].id] += B.query(n) - B.query(tmp2[pos2].x - 1);
      a[pos++] = tmp2[pos2];
      ++pos2;
    }
  }
  while (pos1 <= top1) {
    if (!tmp1[pos1].id) B.modi(tmp1[pos1].x, tmp1[pos1].val);
    a[pos++] = tmp1[pos1];
    ++pos1;
  }
  while (pos2 <= top2) {
    if (tmp2[pos2].id)
      ans[tmp2[pos2].id] += B.query(n) - B.query(tmp2[pos2].x - 1);
    a[pos++] = tmp2[pos2];
    ++pos2;
  }
  for (int i = 1; i <= top1; i++)
    if (!tmp1[i].id) B.modi(tmp1[i].x, -tmp1[i].val);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) val[i] = read();
  for (int i = 1; i <= n; i++) add(val[i], i, 0);
  for (int i = 1; i <= m; i++) {
    int op = read();
    int x = read(), y = read();
    if (op == 1) {
      del(val[x], x, i);
      val[x] = y;
      add(val[x], x, i);
    } else
      a[++top] = (P){x, y, i, ++cnt, 0};
  }
  sort(a + 1, a + top + 1, cmp);
  solve(1, top);
  for (int i = 1; i <= cnt; i++) printf("%lld\n", ans[i]);
  return 0;
}
