#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
long double PI = acos((long double)-1.0);
struct io_s {
  bool negative;
  char ch;
  inline bool isdigitx(char c) { return c >= '0' && c <= '9'; }
  inline char nextchar() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 &&
                   (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
               ? EOF
               : *p1++;
  }
  template <typename T>
  bool rn(T& _v) {
    negative = false;
    _v = 0;
    while (!isdigitx(ch = nextchar()) && ch != EOF) {
      negative = ch == '-';
    };
    if (ch == EOF) return false;
    do {
      _v *= 10;
      _v += ch - '0';
    } while (isdigitx(ch = nextchar()));
    if (negative) _v = -_v;
    return true;
  }
  template <typename T>
  bool run(T& _v) {
    _v = 0;
    while (!isdigitx(ch = nextchar()) && ch != EOF) {
    };
    if (ch == EOF) return false;
    do {
      _v *= 10;
      _v += ch - '0';
    } while (isdigitx(ch = nextchar()));
    return true;
  }
  template <typename T>
  inline T r() {
    T v = T();
    rn(v);
    return v;
  }
  inline int ri() { return r<int>(); }
  inline long long rll() { return r<long long>(); }
  inline int gets(char* s) {
    char* c = s;
    do {
      ch = nextchar();
    } while (ch == '\n' || ch == '\r');
    do {
      *(c++) = ch;
      ch = nextchar();
    } while (ch != '\n' && ch != '\r');
    *(c++) = '\0';
    return c - s - 1;
  }
  inline char get() {
    do {
      ch = nextchar();
    } while (ch < 'A' || ch > 'Z');
    return ch;
  }
  template <class T>
  inline void o(T p) {
    static int stk[70], tp;
    if (p == 0) {
      putchar('0');
      return;
    }
    if (p < 0) {
      p = -p;
      putchar('-');
    }
    while (p) stk[++tp] = p % 10, p /= 10;
    while (tp) putchar(stk[tp--] + '0');
  }
  inline void ln() { putchar('\n'); }
  inline void space() { putchar(' '); }
  template <class T>
  inline void oln(T p) {
    o(p);
    ln();
  }
} io;
using namespace std;
const int N = 100005, M = 10000005;
int ls[M], rs[M], rt[N], n, a[N], m, ndc;
set<int> dat[N];
long long sum[M];
void update(int& x, int l, int r, int p, int u) {
  if (!x) x = ++ndc;
  sum[x] += u;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid)
    update(ls[x], l, mid, p, u);
  else
    update(rs[x], mid + 1, r, p, u);
}
long long ask(int& x, int l, int r, int s, int t) {
  if (!x || l == s && r == t) return sum[x];
  int mid = (l + r) >> 1;
  if (t <= mid) return ask(ls[x], l, mid, s, t);
  if (s > mid) return ask(rs[x], mid + 1, r, s, t);
  return ask(ls[x], l, mid, s, mid) + ask(rs[x], mid + 1, r, mid + 1, t);
}
void modify(int x, int y, int u) {
  while (x <= n) update(rt[x], 1, n, y, u), x += ((x) & -(x));
}
long long query(int x, int y) {
  long long ret = 0;
  while (x) ret += ask(rt[x], 1, n, 1, y), x &= x - 1;
  return ret;
}
void add(int p, int x) {
  dat[p].insert(x);
  auto it = dat[p].find(x), pre = it, suf = it;
  bool f1 = false, f2 = false;
  if (pre != dat[p].begin()) --pre, modify(*pre, x, x - *pre), f1 = 1;
  ++suf;
  if (suf != dat[p].end()) modify(x, *suf, *suf - x), f2 = 1;
  if (f1 && f2) modify(*pre, *suf, -(*suf - *pre));
}
void del(int p, int x) {
  auto it = dat[p].find(x), pre = it, suf = it;
  bool f1 = false, f2 = false;
  if (pre != dat[p].begin()) --pre, modify(*pre, x, -(x - *pre)), f1 = 1;
  ++suf;
  if (suf != dat[p].end()) modify(x, *suf, -(*suf - x)), f2 = 1;
  if (f1 && f2) modify(*pre, *suf, *suf - *pre);
  dat[p].erase(x);
}
int main() {
  io.rn(n);
  io.rn(m);
  for (int i = 1; i <= n; i++) add(a[i] = io.ri(), i);
  for (int i = 1, o, u, v; i <= m; i++) {
    io.rn(o);
    io.rn(u);
    io.rn(v);
    if (o == 1)
      del(a[u], u), a[u] = v, add(a[u], u);
    else {
      int t = n;
      while (t > 0 && (t & (t - 1)) >= v - 1) t &= (t - 1);
      io.oln(query(t, v) - query(u - 1, v));
    }
  }
  return 0;
}
