#include <bits/stdc++.h>
using namespace std;
int n, m;
int shapes[100013], original[100013];
set<int> positions[100013];
int inputQuery[100013][3];
vector<int> values[100013];
long long* tree[4 * 100013 + 2];
int* covers[4 * 100013];
int size[4 * 100013 + 2];
inline long long read(int i, int t) {
  long long sum = 0;
  while (i > 0) {
    sum += tree[t][i];
    i -= i & -i;
  }
  return sum;
}
inline void push_back(int i, int k, int t) {
  int l = size[t];
  while (i < l + 2) {
    tree[t][i] += k;
    i += i & -i;
  }
}
void build(int left, int right, int i) {
  if (left == right) {
    tree[i] = new long long[values[left].size() + 2];
    for (int j = 0; j < values[left].size() + 2; j++) {
      tree[i][j] = 0;
    }
    covers[i] = new int[values[left].size()];
    for (int j = 0; j < values[left].size(); j++) {
      covers[i][j] = values[left][j];
    }
    size[i] = values[left].size();
    return;
  }
  int mid = (left + right) / 2;
  build(left, mid, 2 * i);
  build(mid + 1, right, 2 * i + 1);
  int l1 = size[2 * i];
  int l2 = size[2 * i + 1];
  size[i] = l1 + l2;
  covers[i] = new int[l1 + l2];
  int c1 = 1;
  int max1 = covers[2 * i][0];
  int c2 = 1;
  int max2 = covers[2 * i + 1][0];
  for (int j = 0; j < l1 + l2; j++) {
    covers[i][j] = 0;
    if (max1 < max2) {
      covers[i][j] = max1;
      if (c1 < l1) {
        max1 = covers[2 * i][c1++];
      } else {
        max1 = 1000000000;
      }
    } else {
      covers[i][j] = max2;
      if (c2 < l2) {
        max2 = covers[2 * i + 1][c2++];
      } else {
        max2 = 1000000000;
      }
    }
  }
  tree[i] = new long long[size[i] + 2];
  for (int j = 0; j < size[i] + 2; j++) {
    tree[i][j] = 0;
  }
}
inline int bsearch(int i, int length, int key) {
  int start = 0;
  int end = length - 1;
  while (start <= end) {
    int mid = (start + end) / 2;
    if (covers[i][mid] < key) {
      start = mid + 1;
    } else if (covers[i][mid] == key) {
      return mid;
    } else {
      end = mid - 1;
    }
  }
  return end;
}
void update(int value, int left, int right, int target, int i, int innerVal) {
  if (left == right) {
    push_back(bsearch(i, size[i], value) + 1, innerVal, i);
    return;
  }
  int mid = (left + right) / 2;
  if (left <= target && target <= mid) {
    update(value, left, mid, target, 2 * i, innerVal);
  } else if (mid + 1 <= target && target <= right) {
    update(value, mid + 1, right, target, 2 * i + 1, innerVal);
  } else {
    cout << "wait darn" << endl;
  }
  push_back(bsearch(i, size[i], value) + 1, innerVal, i);
}
inline void update(int value, int target, int innerVal) {
  update(value, 0, n, target, 1, innerVal);
}
int query(int value, int left, int right, int start, int end, int i) {
  if (value > covers[i][size[i] - 1]) {
    return 0;
  }
  if (start <= left && right <= end) {
    return read(size[i] + 1, i) - read(bsearch(i, size[i], value) + 1, i);
  }
  int mid = (left + right) / 2;
  int answer = 0;
  if (left <= end && start <= mid) {
    answer += query(value, left, mid, start, end, 2 * i);
  }
  if (mid + 1 <= end && start <= right) {
    answer += query(value, mid + 1, right, start, end, 2 * i + 1);
  }
  return answer;
}
inline int query(int value, int start, int end) {
  if (start > end) return 0;
  return query(value, 0, n, start, end, 1);
}
int main() {
  if (fopen("boarding.in", "r")) {
    freopen("boarding.in", "r", stdin);
    freopen("boarding.out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> shapes[i];
    original[i] = shapes[i];
    auto it = positions[shapes[i]].upper_bound(-i);
    if (*it < 0) {
      values[i].push_back(-(*it));
    }
    positions[shapes[i]].insert(-i);
    positions[shapes[i]].insert(i);
  }
  for (int i = 0; i < m; i++) {
    cin >> inputQuery[i][0] >> inputQuery[i][1] >> inputQuery[i][2];
  }
  for (int i = 0; i < m; i++) {
    if (inputQuery[i][0] == 1) {
      int changedIndex = inputQuery[i][1];
      int newShape = inputQuery[i][2];
      int oldShape = shapes[changedIndex];
      auto oldShapeFloorIt = positions[oldShape].upper_bound(-changedIndex);
      auto oldShapeCeilingIt = positions[oldShape].upper_bound(changedIndex);
      if (*oldShapeFloorIt < 0 &&
          oldShapeCeilingIt != positions[oldShape].end()) {
        values[*oldShapeCeilingIt].push_back(-(*oldShapeFloorIt));
      }
      positions[oldShape].erase(changedIndex);
      positions[oldShape].erase(-changedIndex);
      auto newShapeFloorIt = positions[newShape].upper_bound(-changedIndex);
      auto newShapeCeilingIt = positions[newShape].upper_bound(changedIndex);
      if (*newShapeFloorIt < 0) {
        values[changedIndex].push_back(-(*newShapeFloorIt));
      }
      if (newShapeCeilingIt != positions[newShape].end()) {
        values[*newShapeCeilingIt].push_back(changedIndex);
      }
      positions[newShape].insert(changedIndex);
      positions[newShape].insert(-changedIndex);
      shapes[changedIndex] = newShape;
    }
  }
  for (int i = 1; i <= n; i++) {
    positions[i].clear();
  }
  for (int i = 1; i <= n; i++) {
    values[i].push_back(i);
    sort(values[i].begin(), values[i].end());
  }
  build(0, n, 1);
  for (int i = 1; i <= n; i++) {
    shapes[i] = original[i];
    auto it = positions[shapes[i]].upper_bound(-i);
    if (*it < 0) {
      update(-(*it), i, i + *it);
    }
    positions[shapes[i]].insert(-i);
    positions[shapes[i]].insert(i);
  }
  for (int i = 0; i < m; i++) {
    if (inputQuery[i][0] == 1) {
      int changedIndex = inputQuery[i][1];
      int newShape = inputQuery[i][2];
      int oldShape = shapes[changedIndex];
      auto oldShapeFloorIt = positions[oldShape].upper_bound(-changedIndex);
      auto oldShapeCeilingIt = positions[oldShape].upper_bound(changedIndex);
      if (oldShapeCeilingIt != positions[oldShape].end()) {
        update(changedIndex, *oldShapeCeilingIt,
               -(*oldShapeCeilingIt - changedIndex));
      }
      if (*oldShapeFloorIt < 0) {
        update(-(*oldShapeFloorIt), changedIndex,
               -(changedIndex + *oldShapeFloorIt));
      }
      if (*oldShapeFloorIt < 0 &&
          oldShapeCeilingIt != positions[oldShape].end()) {
        update(-(*oldShapeFloorIt), *oldShapeCeilingIt,
               *oldShapeCeilingIt + *oldShapeFloorIt);
      }
      positions[oldShape].erase(changedIndex);
      positions[oldShape].erase(-changedIndex);
      auto newShapeFloorIt = positions[newShape].upper_bound(-changedIndex);
      auto newShapeCeilingIt = positions[newShape].upper_bound(changedIndex);
      if (*newShapeFloorIt < 0 &&
          newShapeCeilingIt != positions[newShape].end()) {
        update(-(*newShapeFloorIt), *newShapeCeilingIt,
               -(*newShapeCeilingIt + *newShapeFloorIt));
      }
      if (*newShapeFloorIt < 0) {
        update(-(*newShapeFloorIt), changedIndex,
               changedIndex + *newShapeFloorIt);
      }
      if (newShapeCeilingIt != positions[newShape].end()) {
        update(changedIndex, *newShapeCeilingIt,
               *newShapeCeilingIt - changedIndex);
      }
      positions[newShape].insert(changedIndex);
      positions[newShape].insert(-changedIndex);
      shapes[changedIndex] = newShape;
    } else {
      int l = inputQuery[i][1];
      int r = inputQuery[i][2];
      cout << query(l - 1, 0, n, l, r, 1) << '\n';
    }
  }
}
