I won't feel lonely, nor will I be sorrowful... not before everything is buried.

A string of n beads is left as the message of leaving. The beads are numbered from 1 to n from left to right, each having a shape numbered by integers between 1 and n inclusive. Some beads may have the same shapes.

The memory of a shape x in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape x appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.

From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

Input

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 100 000) — the number of beads in the string, and the total number of changes and queries, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — the initial shapes of beads 1, 2, ..., n, respectively.

The following m lines each describes either a change in the beads or a query of subsegment. A line has one of the following formats: 

  * 1 p x (1 ≤ p ≤ n, 1 ≤ x ≤ n), meaning that the shape of the p-th bead is changed into x; 
  * 2 l r (1 ≤ l ≤ r ≤ n), denoting a query of memory of the subsegment from l to r, inclusive. 

Output

For each query, print one line with an integer — the memory of the recalled subsegment.

Examples

Input

7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7


Output

5
0
7
1


Input

7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7


Output

0
0

Note

The initial string of beads has shapes (1, 2, 3, 1, 3, 2, 1).

Consider the changes and queries in their order: 

  1. 2 3 7: the memory of the subsegment [3, 7] is (7 - 4) + (6 - 6) + (5 - 3) = 5; 
  2. 2 1 3: the memory of the subsegment [1, 3] is (1 - 1) + (2 - 2) + (3 - 3) = 0; 
  3. 1 7 2: the shape of the 7-th bead changes into 2. Beads now have shapes (1, 2, 3, 1, 3, 2, 2) respectively; 
  4. 1 3 2: the shape of the 3-rd bead changes into 2. Beads now have shapes (1, 2, 2, 1, 3, 2, 2) respectively; 
  5. 2 1 6: the memory of the subsegment [1, 6] is (4 - 1) + (6 - 2) + (5 - 5) = 7; 
  6. 2 5 7: the memory of the subsegment [5, 7] is (7 - 6) + (5 - 5) = 1. 
#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);
    }
  }
}
