#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int scan() { return getchar(); }
void scan(int& a) { cin >> a; }
void scan(long long& a) { cin >> a; }
void scan(char& a) { cin >> a; }
void scan(double& a) { cin >> a; }
void scan(long double& a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string& a) { cin >> a; }
template <class T>
void scan(vector<T>&);
template <class T, size_t size>
void scan(array<T, size>&);
template <class T, class L>
void scan(pair<T, L>&);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(deque<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size>& a) {
  for (auto& i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L>& p) {
  scan(p.first);
  scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(T& a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head& head, Tail&... tail) {
  scan(head);
  IN(tail...);
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
template <class T>
void UNIQUE(vector<T>& x) {
  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), x.end());
}
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  unsigned long long x;
  cin >> x;
  return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string& a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T>&);
template <class T, size_t size>
void print(const array<T, size>&);
template <class T, class L>
void print(const pair<T, L>& p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T>& a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size>& a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L>& p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T& a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T& t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head& head, const Tail&... tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
vector<pair<long long, long long>> factor(long long x) {
  vector<pair<long long, long long>> ans;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back({i, 1});
      while ((x /= i) % i == 0) ans.back().second++;
    }
  if (x != 1) ans.push_back({x, 1});
  return ans;
}
vector<int> divisor(int x) {
  vector<int> ans;
  for (int i = 1; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back(i);
      if (i * i != x) ans.push_back(x / i);
    }
  return ans;
}
int popcount(long long x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n)(rng); }
template <class... T>
void err(const T&...) {}
template <typename T>
struct BinaryIndexedTree {
  vector<T> data;
  BinaryIndexedTree(int sz) { data.assign(++sz, 0); }
  T sum(int k) {
    T ret = 0;
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
  void add(int k, T x) {
    for (++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
template <typename structure_t, typename get_t, typename update_t>
struct SegmentTree2DCompressed {
  using merge_f = function<get_t(get_t, get_t)>;
  using range_get_f = function<get_t(structure_t&, int, int)>;
  using update_f = function<void(structure_t&, int, update_t)>;
  int sz;
  vector<structure_t> seg;
  const merge_f f;
  const range_get_f g;
  const update_f h;
  const get_t identity;
  vector<vector<int>> LL, RR;
  vector<vector<int>> beet;
  SegmentTree2DCompressed(int n, const merge_f& f, const range_get_f& g,
                          const update_f& h, const get_t& identity)
      : f(f), g(g), h(h), identity(identity) {
    sz = 1;
    while (sz < n) sz <<= 1;
    beet.resize(2 * sz);
    LL.resize(2 * sz);
    RR.resize(2 * sz);
  }
  void update(int a, int x, update_t z, int k, int l, int r) {
    if (r <= a || a + 1 <= l) return;
    if (a <= l && r <= a + 1) return h(seg[k], x, z);
    update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1);
    update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r);
    return h(seg[k], x, z);
  }
  void update(int x, int y, update_t z) {
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return update(x, y, z, 1, 0, sz);
  }
  get_t query(int a, int b, int x, int y, int k, int l, int r) {
    if (a >= r || b <= l) return identity;
    if (a <= l && r <= b) return g(seg[k], x, y);
    return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1),
             query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r));
  }
  get_t query(int a, int b, int x, int y) {
    x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]);
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return query(a, b, x, y, 1, 0, sz);
  }
  void build() {
    for (int k = (int)beet.size() - 1; k >= sz; k--) {
      sort(begin(beet[k]), end(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
    }
    for (int k = sz - 1; k > 0; k--) {
      beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size());
      merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]),
            begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
      LL[k].resize(beet[k].size() + 1);
      RR[k].resize(beet[k].size() + 1);
      int tail1 = 0, tail2 = 0;
      for (int i = 0; i < beet[k].size(); i++) {
        while (tail1 < beet[2 * k + 0].size() &&
               beet[2 * k + 0][tail1] < beet[k][i])
          ++tail1;
        while (tail2 < beet[2 * k + 1].size() &&
               beet[2 * k + 1][tail2] < beet[k][i])
          ++tail2;
        LL[k][i] = tail1, RR[k][i] = tail2;
      }
      LL[k][beet[k].size()] = (int)beet[2 * k + 0].size();
      RR[k][beet[k].size()] = (int)beet[2 * k + 1].size();
    }
    for (int k = 0; k < beet.size(); k++) {
      seg.emplace_back(structure_t(beet[k].size()));
    }
  }
  void preupdate(int x, int y) { beet[x + sz].push_back(y); }
};
using BIT = BinaryIndexedTree<int>;
auto f = [](int x, int y) { return x + y; };
auto g = [](BIT& k, int x, int y) { return k.sum(y - 1) - k.sum(x - 1); };
auto h = [](BIT& k, int x, int y) { k.add(x, y); };
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  int n, m;
  IN(n, m);
  vector<set<int>> a(n);
  vector<int> mem(n);
  for (long long i = 0; i < n; ++i) {
    int x = in() - 1;
    mem[i] = x;
    a[x].emplace(i);
  }
  using BIT = BinaryIndexedTree<long long>;
  auto g = [](BIT& k, int x, int y) { return k.sum(y - 1) - k.sum(x - 1); };
  auto h = [](BIT& k, int x, long long y) { k.add(x, y); };
  SegmentTree2DCompressed<BIT, long long, long long> seg(
      100002, plus<long long>(), g, h, 0LL);
  for (long long i = 0; i < n; ++i) {
    bool f = true;
    int pre;
    if (a[i].empty()) continue;
    for (auto e : a[i]) {
      if (f)
        pre = e, f = false;
      else {
        seg.preupdate(pre, e);
        pre = e;
      }
    }
  }
  struct query {
    int id, l, r, z;
    query(int l, int r, int z, int id) : id(id), l(l), r(r), z(z) {}
    query(int l, int r, int z) : id(0), l(l), r(r), z(z) {}
  };
  vector<query> Q;
  auto add = [&](int x, int y, int z) {
    query q(x, y, z);
    Q.push_back(q);
  };
  auto b = a;
  while (m--) {
    int id = in();
    if (id == 1) {
      int p = in() - 1;
      int y = mem[p];
      int x = in() - 1;
      mem[p] = x;
      auto it = a[y].find(p);
      if (it != a[y].begin()) {
        it--;
        int pre = *it;
        seg.preupdate(pre, p);
        add(pre, p, pre - p);
        it++;
        it++;
        if (it != a[y].end()) {
          seg.preupdate(pre, *it);
          add(pre, *it, *it - pre);
          add(p, *it, p - *it);
        }
      } else {
        it++;
        if (it != a[y].end()) {
          add(p, *it, p - *it);
        }
      }
      a[y].erase(p);
      it = a[x].lower_bound(p);
      if (it != a[x].begin()) {
        it--;
        int pre = *it;
        seg.preupdate(*it, p);
        add(*it, p, p - *it);
        it++;
        if (it != a[x].end()) {
          seg.preupdate(p, *it);
          add(pre, *it, pre - *it);
          add(p, *it, *it - p);
        }
      } else if (it != a[x].end()) {
        seg.preupdate(p, *it);
        add(p, *it, *it - p);
      }
      a[x].emplace(p);
    } else {
      int l = in() - 1, r = in();
      Q.emplace_back(l, r, 0, 1);
    }
  }
  seg.build();
  for (long long i = 0; i < n; ++i) {
    bool f = true;
    int pre;
    if (b[i].empty()) continue;
    for (auto e : b[i]) {
      if (f)
        pre = e, f = false;
      else {
        seg.update(pre, e, e - pre);
        pre = e;
      }
    }
  }
  for (auto q : Q) {
    if (q.id) {
      cout << seg.query(q.l, q.r, q.l, q.r) << '\n';
    } else {
      seg.update(q.l, q.r, q.z);
    }
  }
}
