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>
using namespace std;
struct cww {
  cww() {
    if (0) {
      ios::sync_with_stdio(false);
      cin.tie(0);
    }
  }
} star;
template <typename T>
inline bool chmin(T &l, T r) {
  bool a = l > r;
  if (a) l = r;
  return a;
}
template <typename T>
inline bool chmax(T &l, T r) {
  bool a = l < r;
  if (a) l = r;
  return a;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &it : v) is >> it;
  return is;
}
namespace RBST {
unsigned yy = 1145141919;
inline unsigned xorshift() {
  yy = yy ^ (yy << 13);
  yy = yy ^ (yy >> 17);
  return yy = yy ^ (yy << 5);
}
constexpr int MASK = 65535;
inline int randInt() { return (int)(xorshift() & MASK); }
const int RBST_SIZE = 2123456;
struct node {
  int val, lb, ub;
  long long latte, sum;
  int sz;
  node *lc, *rc;
  node *p;
};
typedef pair<node *, node *> pn;
inline int size(node *v) { return !v ? 0 : v->sz; }
inline node *update(node *v) {
  if (!v) return v;
  v->sz = 1 + size(v->lc) + size(v->rc);
  v->ub = !(v->rc) ? v->val : v->rc->ub;
  v->lb = !(v->lc) ? v->val : v->lc->lb;
  v->sum = v->latte;
  v->sum += !(v->lc) ? 0 : v->lc->sum;
  v->sum += !(v->rc) ? 0 : v->rc->sum;
  if (v->rc != NULL) v->rc->p = v;
  if (v->lc != NULL) v->lc->p = v;
  v->p = NULL;
  return v;
}
namespace pool {
node mem[RBST_SIZE], *que[RBST_SIZE];
int bg = 0;
struct RB {
  RB() {
    for (int i = (0); i < (RBST_SIZE); i++) que[i] = &mem[i];
  }
} ST;
void push(node *m) { que[--bg] = m; }
node *get(node val) {
  node *ret = que[bg++];
  *ret = val;
  return ret;
}
node *get(int v, long long val) {
  return get(node{v, v, v, val, val, 1, NULL, NULL, NULL});
}
}  // namespace pool
inline int lr(long long a, long long b) {
  return randInt() * (a + b) < a * MASK;
}
node *merge(node *l, node *r) {
  if (!l || !r) return !l ? update(r) : update(l);
  node *ret;
  if (lr(l->sz, r->sz)) {
    l->rc = merge(l->rc, r);
    ret = update(l);
  } else {
    r->lc = merge(l, r->lc);
    ret = update(r);
  }
  return ret;
}
pn split(node *v, int key) {
  if (!v) return pn(NULL, NULL);
  if (v->val < key) {
    pn s = split(v->rc, key);
    v->rc = s.first;
    return pn(update(v), s.second);
  } else {
    pn s = split(v->lc, key);
    v->lc = s.second;
    return pn(s.first, update(v));
  }
}
node *lower_bound(node *v, int key) {
  if (!v) return v;
  if (v->val < key) {
    return lower_bound(v->rc, key);
  } else {
    node *u = lower_bound(v->lc, key);
    return !u ? v : u;
  }
}
node *min(node *v) { return !v->lc ? v : min(v->lc); }
node *max(node *v) { return !v->rc ? v : max(v->rc); }
node *nxt(node *v, node *p = NULL) {
  if (!p) {
    if (v->rc != NULL) return min(v->rc);
  } else {
    if (v->lc == p) return v;
  }
  return !v->p ? NULL : nxt(v->p, v);
}
node *prv(node *v, node *p = NULL) {
  if (!p) {
    if (v->lc != p) return max(v->lc);
  } else {
    if (v->rc == p) return v;
  }
  return !v->p ? NULL : prv(v->p, v);
}
struct RBST {
  node *root;
  RBST() { root = NULL; }
  bool isempty() { return !root; }
  int size() {
    if (isempty())
      return 0;
    else
      root->sz;
  }
  bool exist(int key) {
    node *v = lower_bound(root, key);
    return v && v->val == key;
  }
  bool erase(int key) {
    auto l_mr = split(root, key);
    auto m_r = split(l_mr.second, key + 1);
    root = merge(l_mr.first, m_r.second);
    if (!m_r.first)
      return false;
    else {
      pool::push(m_r.first);
      return true;
    }
  }
  bool insert(int key, long long val) {
    node *ins = pool::get(key, val);
    auto l_r = split(root, key);
    root = merge(merge(l_r.first, ins), l_r.second);
    return true;
  }
  long long get(int a, int b, node *v) {
    if (v == NULL) return 0;
    if (a <= v->lb && v->ub <= b) {
      return v->sum;
    }
    if (v->ub < a || b < v->lb) {
      return 0;
    }
    long long ret = a <= v->val && v->val <= b ? v->latte : 0;
    ret += get(a, b, v->lc);
    ret += get(a, b, v->rc);
    return ret;
  }
  long long get(int a, int b) { return get(a, b, root); }
};
}  // namespace RBST
struct node {
  RBST::RBST b;
};
long long mg(node &v, int key) { return v.b.get(-1, key); }
long long mg(long long l, long long r) { return l + r; }
namespace ST {
node mem[1][2123456];
int cnt = 0;
node *get() { return mem[cnt++]; }
}  // namespace ST
struct seg_tree {
  int size;
  node *seg;
  void init(int l, int r, int k = 0) {
    auto &v = seg[k];
    v.b = RBST::RBST();
    if (r - l == 1) {
    } else if (r - l > 1) {
      int m = (l + r) / 2;
      init(l, m, k * 2 + 1);
      init(m, r, k * 2 + 2);
    }
  }
  seg_tree(int n) {
    size = 1;
    while (size < n) size *= 2;
    seg = ST::get();
    init(0, size);
  }
  long long get(int a, int b, int k, int l, int r) {
    if (a <= l) {
      if (0)
        cout << l << r << " " << seg[k].b.size() << " " << mg(seg[k], b - 1)
             << "\n";
      return mg(seg[k], b - 1);
    }
    int m = (l + r) / 2;
    bool ll = !(m <= a);
    bool rr = !(r <= a);
    long long ret;
    if (ll && rr)
      ret = mg(get(a, b, k * 2 + 1, l, m), get(a, b, k * 2 + 2, m, r));
    else if (ll)
      ret = get(a, b, k * 2 + 1, l, m);
    else
      ret = get(a, b, k * 2 + 2, m, r);
    return ret;
  }
  long long get(int a, int b) { return get(a, b, 0, 0, size); }
  void ins(int a, int b, int k, int l, int r, long long key, long long val) {
    if (r <= a || b <= l) return;
    seg[k].b.insert(key, val);
    if (a <= l && r <= b) {
    } else {
      int m = (l + r) / 2;
      ins(a, b, k * 2 + 1, l, m, key, val);
      ins(a, b, k * 2 + 2, m, r, key, val);
    }
  }
  void ins(int a, int b, long long val) {
    node q;
    ins(a, a + 1, 0, 0, size, b - 1, val);
  }
  void del(int a, int b, int k, int l, int r, long long key) {
    if (r <= a || b <= l) return;
    seg[k].b.erase(key);
    if (a <= l && r <= b) {
    } else {
      int m = (l + r) / 2;
      del(a, b, k * 2 + 1, l, m, key);
      del(a, b, k * 2 + 2, m, r, key);
    }
  }
  void del(int a, int b) {
    node q;
    del(a, a + 1, 0, 0, size, b - 1);
  }
};
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<int> v(n);
  vector<set<int>> x(n);
  seg_tree seg(n + 10);
  for (int i = (0); i < (n); i++) {
    int a;
    scanf("%d", &a);
    a--;
    v[i] = a;
    x[a].insert(i);
  }
  for (int i = (0); i < (n); i++) {
    int prv = -1;
    for (auto &now : x[i]) {
      if (prv >= 0) {
        int len = now - prv;
        seg.ins(prv, now + 1, len);
      }
      prv = now;
    }
  }
  auto check = [&]() {
    for (int l = (1); l < (n + 1); l++)
      for (int r = (l); r < (n + 1); r++) {
        vector<set<int>> s(n);
        for (int i = (l - 1); i < (r); i++) s[v[i]].insert(i);
        long long ans = 0;
        for (int i = (0); i < (n); i++)
          if (s[i].size()) {
            ans += (*s[i].rbegin()) - (*s[i].begin());
          }
        if (ans != seg.get(l - 1, r)) {
          return false;
        }
      }
    return true;
  };
  for (int i = (0); i < (q); i++) {
    int type;
    scanf("%d", &type);
    if (type == 2) {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%lld\n", seg.get(l - 1, r));
    } else {
      int p, val;
      scanf("%d%d", &p, &val);
      p--;
      val--;
      if (v[p] == val) continue;
      {
        auto &td = x[v[p]];
        {
          auto ym = td.find(p);
          if (ym != td.begin()) {
            auto yb = ym;
            yb--;
            seg.del(*yb, (*ym) + 1);
          }
          {
            auto ye = ym;
            ye++;
            if (ye != td.end()) {
              seg.del(*ym, (*ye) + 1);
              if (ym != td.begin()) {
                auto yb = ym;
                yb--;
                seg.ins(*yb, (*ye) + 1, (*ye - (*yb)));
              }
            }
          }
        }
        td.erase(p);
      }
      v[p] = val;
      {
        auto &td = x[val];
        td.insert(p);
        {
          auto ym = td.find(p);
          if (ym != td.begin()) {
            auto yb = ym;
            yb--;
            seg.ins(*yb, (*ym) + 1, *ym - *yb);
          }
          {
            auto ye = ym;
            ye++;
            if (ye != td.end()) {
              if (ym != td.begin()) {
                auto yb = ym;
                yb--;
                seg.del(*yb, (*ye) + 1);
              }
              seg.ins(*ym, (*ye) + 1, *ye - *ym);
            }
          }
        }
      }
    }
  }
  return 0;
}
