#include <bits/stdc++.h>
using namespace std;
int n;
int occ[167][(167 * 600)], ind[(167 * 600)], lef[(167 * 600)], arr[(167 * 600)];
vector<pair<int, int> > v[167];
void pre(int in) {
  int i, l = in * 600, r = (in + 1) * 600;
  v[in].clear();
  for (i = l; i < r; i++) v[in].push_back(make_pair(lef[i], i - lef[i]));
  sort(v[in].begin(), v[in].end());
  for (i = v[in].size() - 2; i >= 0; i--)
    v[in][i].second += v[in][i + 1].second;
}
void update(int in, int ele) {
  set<int> s;
  int i, j, f = 1, bb = ((in / 600) + 1) * 600, pre_ele = arr[in];
  occ[in / 600][pre_ele]--;
  for (i = in + 1; f && i < bb; i++) {
    if (arr[i] == pre_ele) {
      lef[i] = lef[in];
      s.insert(i / 600);
      f = 0;
    }
  }
  for (i = bb / 600; f && i < 167; i++)
    if (occ[i][pre_ele] > 0) {
      for (j = i * 600; f; j++)
        if (arr[j] == pre_ele) {
          lef[j] = lef[in];
          s.insert(j / 600);
          f = 0;
        }
    }
  f = 1;
  arr[in] = ele;
  occ[in / 600][ele]++;
  for (i = in + 1; f && i < bb; i++) {
    if (arr[i] == ele) {
      lef[i] = in;
      s.insert(i / 600);
      f = 0;
    }
  }
  for (i = bb / 600; f && i < 167; i++)
    if (occ[i][ele] > 0) {
      for (j = i * 600; f && j < (i + 1) * 600; j++)
        if (arr[j] == ele) {
          lef[j] = in;
          s.insert(j / 600);
          f = 0;
        }
    }
  lef[in] = -1;
  f = 1;
  for (i = in - 1; f && i >= (in / 600) * 600; i--) {
    if (arr[i] == ele) {
      lef[in] = i;
      f = 0;
    }
  }
  for (i = in / 600 - 1; i >= 0; i--) {
    if (occ[i][ele] > 0) {
      for (j = (i + 1) * 600 - 1; f && j >= i * 600; j--)
        if (arr[j] == ele) {
          lef[in] = j;
          f = 0;
        }
    }
  }
  s.insert(in / 600);
  set<int>::iterator it;
  for (it = s.begin(); it != s.end(); it++) pre(*it);
}
int loww(int in, int lval) {
  int l = 0, r = v[in].size() - 1, ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (v[in][mid].first < lval)
      l = mid + 1;
    else {
      ans = mid;
      r = mid - 1;
    }
  }
  return ans;
}
long long int func(int l, int r) {
  long long int ans = 0, i;
  for (i = l; i % 600 != 0 && i <= r; i++)
    if (lef[i] >= l) ans = ans + i - lef[i];
  for (; (i + 600 - 1) <= r; i += 600) {
    int ind = i / 600;
    int j = loww(ind, l);
    if (j != -1) ans = ans + v[ind][j].second;
  }
  for (; i <= r; i++) {
    if (lef[i] >= l) ans += i - lef[i];
  }
  return ans;
}
int main() {
  int i, m;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
    ind[i + 1] = -3;
    occ[i / 600][arr[i]]++;
  }
  for (i = 0; i < n; i++) {
    lef[i] = ind[arr[i]];
    ind[arr[i]] = i;
  }
  for (i = 0; i < 167; i++) pre(i);
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a == 1) {
      b--;
      update(b, c);
    } else {
      long long int ans = func(b - 1, c - 1);
      printf("%lld\n", ans);
    }
  }
  return 0;
}
