#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct node {
  long long sum;
  node *left, *right;
  node(node *left, node *right, long long _sum)
      : left(left), right(right), sum(_sum) {}
};
node *it[maxn];
node *null = new node(NULL, NULL, 0);
int n, m, a[maxn];
set<int> mem[maxn];
void IT_update(node *S, int l, int r, int u, int val) {
  if (u < l || u > r) return;
  if (l == r) {
    S->sum += val;
    return;
  }
  int mid = (l + r) / 2;
  if (u <= mid && S->left == null) S->left = new node(null, null, 0);
  IT_update(S->left, l, mid, u, val);
  if (u > mid && S->right == null) S->right = new node(null, null, 0);
  IT_update(S->right, mid + 1, r, u, val);
  S->sum = S->left->sum + S->right->sum;
}
long long IT_Get(node *S, int l, int r, int lo, int hi) {
  if (hi < l || lo > r) return 0;
  if (lo <= l && r <= hi) return S->sum;
  int mid = (l + r) / 2;
  long long res = 0;
  if (S->left != null) res += IT_Get(S->left, l, mid, lo, hi);
  if (S->right != null) res += IT_Get(S->right, mid + 1, r, lo, hi);
  return res;
}
void BIT_update(int i, int R, int val) {
  while (i <= n) {
    IT_update(it[i], 1, n, R, val);
    i += i & (-i);
  }
}
long long BIT_Get(int i, int R) {
  long long res = 0;
  while (i > 0) {
    res += IT_Get(it[i], 1, n, 1, R);
    i -= i & (-i);
  }
  return res;
}
void change(int type, int a, int id) {
  if (type == 1) mem[a].insert(id);
  auto pos = mem[a].find(id);
  auto prv = pos, nxt = pos;
  int t1 = 0, t2 = 0;
  if (prv != mem[a].begin()) {
    prv--;
    BIT_update(*prv, id, type * (id - *prv));
    t1 = 1;
  }
  nxt++;
  if (nxt != mem[a].end()) {
    BIT_update(id, *nxt, type * (*nxt - id));
    t2 = 1;
  }
  if (t1 + t2 == 2) BIT_update(*prv, *nxt, type * (*prv - *nxt));
  if (type == -1) mem[a].erase(id);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) it[i] = new node(null, null, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    change(1, a[i], i);
  }
  for (int i = 1; i <= m; i++) {
    int tt, l, r;
    cin >> tt >> l >> r;
    if (tt == 1) {
      change(-1, a[l], l);
      a[l] = r;
      change(1, r, l);
    }
    if (tt == 2) cout << BIT_Get(r, r) - BIT_Get(l - 1, r) << endl;
  }
}
