#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100 * 1000 + 10;
const int MAX_BLOCK = 320;
using lint = long long;
class TTree {
 private:
  lint Data[1024];
  lint PushData[1024];
  int Start;
  int Size;

 private:
  int ChildLeft(int index) const;
  int ChildRight(int index) const;
  int Parent(int index) const;
  void Push(int index, int cnt);
  void Add(int index, int rL, int rR, int l, int r, lint value);

 public:
  void Resize(int start, int size);
  TTree() {}
  void Add(int l, int r, lint value);
  lint Get(int index) const;
  void show() { int cnt = 0; }
};
void TTree::Resize(int start, int finish) {
  Start = start;
  int size = finish - start + 1;
  for (Size = 1; Size < size; Size *= 2)
    ;
  for (int i = 0; i < 2 * Size - 1; ++i) {
    Data[i] = PushData[i] = 0;
  }
}
int TTree::ChildLeft(int index) const { return (index * 2 + 1); }
int TTree::ChildRight(int index) const { return (index * 2 + 2); }
int TTree::Parent(int index) const { return (index - 1) / 2; }
void TTree::Push(int index, int cnt) {
  int lc = ChildLeft(index);
  int rc = ChildRight(index);
  Data[index] += PushData[index] * cnt;
  if (rc <= 2 * Size - 2) {
    PushData[lc] += PushData[index];
    PushData[rc] += PushData[index];
  }
  PushData[index] = 0;
}
void TTree::Add(int l, int r, lint value) {
  if (l <= r) {
    Add(0, 0, Size - 1, l, r, value);
  }
}
void TTree::Add(int index, int rL, int rR, int l, int r, lint value) {
  if (rR < l || r < rL) {
    return;
  }
  if (l <= rL && rR <= r) {
    PushData[index] += value;
    return;
  }
  Push(index, rR - rL + 1);
  int mid = (rL + rR) / 2;
  Add(ChildLeft(index), rL, mid, l, r, value);
  Add(ChildRight(index), mid + 1, rR, l, r, value);
}
lint TTree::Get(int index) const {
  index += Size - 1;
  lint value = Data[index] + PushData[index];
  do {
    index = Parent(index);
    value += PushData[index];
  } while (index != Parent(index));
  return value;
}
int N, sqrtN;
TTree T[MAX_BLOCK];
int a[MAX_N];
set<int> Positions[MAX_N];
set<int> RevPositions[MAX_N];
int GetMin(int value, int position) {
  auto it = RevPositions[value].upper_bound(-position);
  if (it == RevPositions[value].end()) {
    return -1;
  }
  return -(*it);
}
int GetMax(int value, int position) {
  auto it = Positions[value].upper_bound(position);
  if (it == Positions[value].end()) {
    return -1;
  }
  return (*it);
}
void RemovePosition(int value, int position) {
  Positions[value].erase(position);
  RevPositions[value].erase(-position);
}
void AddPosition(int value, int position) {
  Positions[value].insert(position);
  RevPositions[value].insert(-position);
}
int Block(int position) { return position / sqrtN; }
void Change(int startBlock, int value, int position, int minus = -1) {
  int minP = GetMin(value, position);
  if (minP < startBlock * sqrtN) {
    minP = -1;
  }
  int maxP = GetMax(value, position);
  if (minP == -1 && maxP == -1) {
    return;
  }
  int left = Block(position), right = Block(N), diff = position - minP;
  if (minP == -1) {
    diff = maxP - position;
    left = Block(maxP);
  }
  if (minP != -1 && maxP != -1) {
    right = Block(maxP) - 1;
  }
  diff *= minus;
  T[startBlock].show();
  T[startBlock].Add(left, right, diff);
  T[startBlock].show();
}
void Change(int position, int newValue) {
  int lastValue = a[position];
  RemovePosition(lastValue, position);
  for (int b = 0; b <= sqrtN; ++b) {
    if (b * sqrtN <= position) {
      Change(b, lastValue, position);
      Change(b, newValue, position, 1);
    }
  }
  AddPosition(newValue, position);
  a[position] = newValue;
}
lint Get(int l, int r) {
  int lb = Block(l) + 1, rb = Block(r) - 1;
  int ll = lb * sqrtN, rr = (rb + 1) * sqrtN - 1;
  lint answer = 0;
  if (ll <= rr) {
    answer = T[lb].Get(rb);
  }
  for (int i = l; i < min(ll, r + 1); ++i) {
    int maxP = GetMax(a[i], i);
    if (maxP <= r && maxP != -1) {
      answer += maxP - i;
    }
  }
  for (int i = r; i > max(rr, ll - 1); --i) {
    int minP = GetMin(a[i], i);
    if (minP >= ll) {
      answer += i - minP;
    }
  }
  return answer;
}
lint StupidGet(int l, int r) {
  lint answer = 0;
  set<int> v;
  for (int i = l; i <= r; ++i) {
    if (!v.count(a[i])) {
      int index = i;
      for (int j = i + 1; j <= r; ++j) {
        if (a[i] == a[j]) {
          index = j;
        }
      }
      answer += index - i;
      v.insert(a[i]);
    }
  }
  return answer;
}
int main() {
  int M;
  N = 14;
  scanf("%d%d", &N, &M);
  sqrtN = sqrt(double(N)) + 1;
  for (int i = 0; i <= sqrtN + 1; ++i) {
    T[i].Resize(i, sqrtN + 1);
  }
  for (int i = 0, aa; i < N; ++i) {
    aa = rand() % N + 1;
    scanf("%d", &aa);
    Change(i, aa);
  }
  for (int i = 0, t = 2, l, r; i < M; ++i) {
    l = rand() % N + 1;
    r = rand() % (N - l + 1) + l;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      Change(l - 1, r);
    }
    if (t == 2) {
      lint answer = Get(l - 1, r - 1);
      printf("%I64d\n", answer);
    }
  }
  return 0;
}
