#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 7;
mt19937 rnd;
struct Node {
  Node *L, *R;
  long long x, y, cost, sum;
  Node(long long l, long long r) {
    L = R = nullptr;
    x = r;
    y = rnd();
    cost = r - l;
    sum = cost;
  }
};
void recalc(Node* v) {
  if (v) v->sum = (v->L ? v->L->sum : 0) + (v->R ? v->R->sum : 0) + v->cost;
}
Node* merge(Node* Left, Node* Right) {
  if (!Left || !Right) return (Left ? Left : Right);
  if (Left->y > Right->y) {
    Left->R = merge(Left->R, Right);
    recalc(Left);
    return Left;
  } else {
    Right->L = merge(Left, Right->L);
    recalc(Right);
    return Right;
  }
}
pair<Node*, Node*> split(Node* root, long long x) {
  if (!root) return make_pair(nullptr, nullptr);
  if (root->x <= x) {
    pair<Node*, Node*> splitted = split(root->R, x);
    root->R = splitted.first;
    recalc(root);
    return make_pair(root, splitted.second);
  } else {
    pair<Node*, Node*> splitted = split(root->L, x);
    root->L = splitted.second;
    recalc(root);
    return make_pair(splitted.first, root);
  }
}
void insert(Node*& root, long long l, long long r) {
  pair<Node*, Node*> splitted1 = split(root, r);
  pair<Node*, Node*> splitted2 = split(splitted1.first, r - 1);
  root = merge(splitted2.first, merge(new Node(l, r), splitted1.second));
}
void erase(Node*& root, long long r) {
  pair<Node*, Node*> splitted1 = split(root, r);
  pair<Node*, Node*> splitted2 = split(splitted1.first, r - 1);
  root = merge(splitted2.first, splitted1.second);
}
long long cnt(Node*& root, long long x) {
  pair<Node*, Node*> splitted = split(root, x);
  long long ans = (splitted.first ? splitted.first->sum : 0);
  root = merge(splitted.first, splitted.second);
  return ans;
}
set<long long> vals[MAXN];
long long ps = MAXN, n;
long long a[MAXN], r[MAXN], cost[MAXN], nxt[MAXN];
Node* t[4 * MAXN];
void ers(long long v, long long tl, long long tr, long long p, long long val) {
  erase(t[v], val);
  if (tl != tr) {
    long long tm = (tl + tr) / 2;
    if (p <= tm)
      ers(2 * v, tl, tm, p, val);
    else
      ers(2 * v + 1, tm + 1, tr, p, val);
  }
}
void isrt(long long v, long long tl, long long tr, long long p, long long val) {
  insert(t[v], p, val);
  if (tl != tr) {
    long long tm = (tl + tr) / 2;
    if (p <= tm)
      isrt(2 * v, tl, tm, p, val);
    else
      isrt(2 * v + 1, tm + 1, tr, p, val);
  }
}
bool isller(long long a, long long b, long long c, long long d) {
  return (a <= c && c <= b) || (a <= d && d <= b) || (c <= a && a <= d);
}
bool AinB(long long a, long long b, long long c, long long d) {
  return (c <= a && b <= d);
}
long long get(long long v, long long tl, long long tr, long long l,
              long long r) {
  if (!isller(tl, tr, l, r))
    return 0;
  else if (AinB(tl, tr, l, r))
    return cnt(t[v], r);
  else {
    long long tm = (tl + tr) / 2;
    return get(2 * v, tl, tm, l, r) + get(2 * v + 1, tm + 1, tr, l, r);
  }
}
void update(long long p, long long r) {
  ers(1, 0, n - 1, p, nxt[p]);
  nxt[p] = r;
  isrt(1, 0, n - 1, p, r);
}
void solve() {
  long long m;
  cin >> n >> m;
  for (long long i = 0; i < n; ++i) nxt[i] = -1;
  for (long long i = 0; i < n; ++i) cin >> a[i];
  for (long long i = 0; i < n; ++i) vals[a[i]].insert(i);
  for (long long i = 0; i < n; ++i) {
    auto it = vals[a[i]].find(i);
    ++it;
    if (it == vals[a[i]].end())
      update(i, ++ps);
    else
      update(i, *it);
  }
  for (long long i = 0; i < m; ++i) {
    long long type;
    cin >> type;
    if (type == 1) {
      long long p, x;
      cin >> p >> x;
      --p;
      auto it = vals[a[p]].find(p);
      if (it == vals[a[p]].begin()) {
      } else if (next(it) == vals[a[p]].end()) {
        update(*prev(it), ++ps);
      } else {
        update(p, ++ps);
        update(*prev(it), *next(it));
      }
      update(p, ++ps);
      vals[a[p]].erase(p);
      a[p] = x;
      vals[a[p]].insert(p);
      it = vals[a[p]].find(p);
      if (it == vals[a[p]].begin()) {
      } else if (next(it) == vals[a[p]].end()) {
        update(*prev(it), p);
      } else {
        update(*prev(it), p);
        update(p, *next(it));
      }
    } else {
      long long l, r;
      cin >> l >> r;
      --l;
      --r;
      cout << get(1, 0, n - 1, l, r) << "\n";
    }
  }
  return;
}
signed main() {
  ios_base::sync_with_stdio(false);
  solve();
  return 0;
}
