#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, modd = 1e9 + 7, SIZE = 1e5 + 100, inf = 0x3f3f3f3f,
          INF = 0x7fffffff, hmod1 = 0x48E2DCE7, hmod2 = 0x60000005;
const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const double eps = 1e-8;
template <class T>
inline void sc(T &x) {
  char c;
  x = 0;
  while ((c = getchar()) < '0')
    ;
  while (c >= '0' && c <= '9') x = x * 10 + (c - 48), c = getchar();
}
inline long long min(long long a, long long b) { return a < b ? a : b; }
inline long long max(long long a, long long b) { return a > b ? a : b; }
inline long long gcd(long long a, long long b) {
  return b == 0 ? a : gcd(b, a % b);
}
inline long long exgcd(long long a, long long b, long long &x, long long &y) {
  long long d;
  (b == 0 ? (x = 1, y = 0, d = a)
          : (d = exgcd(b, a % b, y, x), y -= a / b * x));
  return d;
}
inline long long qpow(long long a, long long n) {
  long long sum = 1;
  while (n) {
    if (n & 1) sum = sum * a % modd;
    a = a * a % modd;
    n >>= 1;
  }
  return sum;
}
inline long long qmul(long long a, long long n) {
  long long sum = 0;
  while (n) {
    if (n & 1) sum = (sum + a) % modd;
    a = (a + a) % modd;
    n >>= 1;
  }
  return sum;
}
inline long long inv(long long a) { return qpow(a, modd - 2); }
inline long long madd(long long a, long long b) {
  return (a % modd + b % modd) % modd;
}
inline long long mmul(long long a, long long b) { return a % modd * b % modd; }
inline void uadd(long long &a, long long b) { a = madd(a, b); }
inline void umul(long long &a, long long b) { a = mmul(a, b); }
inline void umin(long long &a, long long b) { a = min(a, b); }
inline void umax(long long &a, long long b) { a = max(a, b); }
struct Query {
  long long type;
  long long x, y, v;
  bool operator<(const Query &a) const {
    if (x != a.x)
      return x < a.x;
    else if (y != a.y)
      return y < a.y;
    else if (type != a.type)
      return type > a.type;
    else
      return v < a.v;
  }
} q[maxn << 3];
long long n, m, tot, tota, ans[maxn], d[maxn], num[maxn], pre[maxn];
set<int> st[maxn];
void add(int x, int v) {
  x += 3;
  while (x <= n + 10) {
    d[x] += v;
    x += (x & (-x));
  }
}
long long query(long long x) {
  x += 3;
  long long res = 0;
  while (x) {
    res += d[x];
    x -= (x & (-x));
  }
  return res;
}
void cdq(int l, int r) {
  if (l == r) return;
  int m = (l + r) >> 1;
  cdq(l, m);
  cdq(m + 1, r);
  int j = l;
  for (int i = m + 1; i <= r; i++) {
    if (q[i].type == 2) continue;
    for (; j <= m && q[j].x <= q[i].x; j++)
      if (q[j].type == 2) add(q[j].y, q[j].v * (q[j].x - q[j].y));
    ans[q[i].v] += ((q[i].type << 1) - 1) * query(q[i].y);
  }
  for (int i = l; i < j; i++)
    if (q[i].type == 2) add(q[i].y, -q[i].v * (q[i].x - q[i].y));
  inplace_merge(q + l, q + m + 1, q + r + 1);
}
inline void print(int t, int a, int b) {}
void addm(int a, int b) {
  if (num[a] == b) return;
  q[++tot] = {2, a, pre[a], -1};
  print(-1, a, pre[a]);
  auto it = st[num[a]].upper_bound(a);
  if (it != st[num[a]].end()) {
    q[++tot] = {2, *it, pre[*it], -1};
    print(-1, *it, pre[*it]);
    pre[*it] = pre[a];
    q[++tot] = {2, *it, pre[*it], 1};
    print(1, *it, pre[*it]);
  }
  st[num[a]].erase(a);
  it = st[b].upper_bound(a);
  if (it != st[b].end()) {
    pre[a] = pre[*it];
    q[++tot] = {2, a, pre[a], 1};
    print(1, a, pre[a]);
    q[++tot] = {2, *it, pre[*it], -1};
    print(-1, *it, pre[*it]);
    pre[*it] = a;
    q[++tot] = {2, *it, pre[*it], 1};
    print(1, *it, pre[*it]);
  } else if (!st[b].empty()) {
    pre[a] = *prev(st[b].end());
    q[++tot] = {2, a, pre[a], 1};
    print(1, a, pre[a]);
  } else {
    pre[a] = 0;
    q[++tot] = {2, a, pre[a], 1};
    print(1, a, pre[a]);
  }
  num[a] = b;
  st[b].insert(a);
}
void addq(int l, int r) {
  q[++tot] = {1, r, r, ++tota};
  q[++tot] = {1, l - 1, l - 1, tota};
  q[++tot] = {0, r, l - 1, tota};
  q[++tot] = {0, l - 1, r, tota};
}
int main() {
  int o, a, b;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> num[i];
    pre[i] = st[num[i]].empty() ? 0 : *prev(st[num[i]].end());
    q[++tot] = {2, i, pre[i], 1};
    st[num[i]].insert(i);
  }
  while (m--) {
    cin >> o >> a >> b;
    if (o == 1)
      addm(a, b);
    else
      addq(a, b);
  }
  cdq(1, tot);
  for (int i = 1; i <= tota; i++) cout << ans[i] << endl;
}
