 ///	BE		NAME		KHODA
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
//#define int ll
const int maxn = 1e5 + 1000, sq = 320;

int n, q;
int a[maxn], last[maxn], dist[maxn], pdist[maxn];
set < int > index[maxn];
pair < int , int > arr[maxn];

int bnum(int x) {
	return x / sq;
}

int startofb(int x) {
	return x * sq;
}

int endofb(int x) {
	return min(startofb(x) + sq, n);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n >> q;
  for(int i = 0; i < n; ++i) {
		cin >> a[i];
		index[a[i]].insert(i);
  }
  set < int > :: iterator it;
  for(int i = 0; i < n; ++i) {
		it = index[a[i]].lower_bound(i);
		if(it != index[a[i]].begin()) {
			it --;
			last[i] = *it;
			dist[i] = i - last[i];
		}
		else {
			dist[i] = i;
			last[i] = -1;
		}
  }
  for(int i = 0; i < n; ++i) {
		arr[i] = {last[i], dist[i]};
  }
  for(int i = 0; i < n / sq + 1; ++i) {
		sort(arr + startofb(i), arr + endofb(i));
		int sar = startofb(i), tah = endofb(i);
		pdist[sar] = arr[sar].ss;
		for(int j = sar + 1; j < tah; ++j) {
			pdist[j] = pdist[j - 1] + arr[j].ss;
		}
  }
  /*for(int i = 0; i < n; ++i) {
		cout << last[i] << ' ';
  }
  cout << endl;
  for(int i = 0; i < n; ++i) {
		cout << dist[i] << ' ' ;
  }
  cout << endl;
  for(int i = 0; i < n; ++i) {
		cout << arr[i].ff << ' ' ;
  }
  cout << endl;
  for(int i = 0; i < n; ++i) {
		cout << arr[i].ss << ' ' ;
  }
  cout << endl;
  for(int i = 0; i < n; ++i) {
		cout << pdist[i] << ' ' ;
  }
  cout << endl;
  cout << endl;*/
  while(q --) {
		int type;
		cin >> type;
		if(type == 1) {
			int p, x, pp = -1, ppp = -1;
			cin >> p >> x;
			-- p;
			if(a[p] == x) {
				continue;
			}
			it = index[a[p]].upper_bound(p);
			if(it != index[a[p]].end()) {
				last[*it] = last[p];
				dist[*it] = dist[*it] + dist[p];
				pp = *it;
			}
			if(index[x].size() == 0) {
				dist[p] = p;
				last[p] = 0;
			}
			else {
				it = index[x].lower_bound(p);
				if(it == index[x].begin()) {
					last[*it] = p;
					dist[*it] = *it - p;
					ppp = *it;
					last[p] = -1;
					dist[p] = p;
				}
				else if(it == index[x].end()) {
					it --;
					last[p] = *it;
					dist[p] = p - *it;
				}
				else {
					last[*it] = p;
					dist[*it] = *it - p;
					ppp = *it;
					it --;
					last[p] = *it;
					dist[p] = p - *it;
				}
			}
			index[x].insert(p);
			index[a[p]].erase(p);
			a[p] = x;
			int qq[3]; qq[0] = p; qq[1] = pp; qq[2] = ppp;
			for(int jj = 0; jj < 3; ++jj) {
				if(qq[jj] == -1) {
					continue;
				}
				int xx = qq[jj];
				int sar = startofb(bnum(xx)), tah = endofb(bnum(xx));
				for(int i = sar; i < tah; ++i) {
					arr[i] = {last[i], dist[i]};
				}
				sort(arr + sar, arr + tah);
				pdist[sar] = arr[sar].ss;
				for(int j = sar + 1; j < tah; ++j) {
					pdist[j] = pdist[j - 1] + arr[j].ss;
				}
			}
		}
		else {
			int l, r;
			cin >> l >> r;
			-- l;
			if(r - l < sq * 2 + 3) {
				int res = 0;
				for(int i = l; i < r; ++i) {
					if(last[i] >= l) {
						res += dist[i];
					}
				}
				cout << res << endl;
			}
			else {
				//cout << "here " << l << ' ' << r << endl;
				int res = 0;
				for(int i = l; i < startofb(bnum(l) + 1); ++i) {
					if(last[i] >= l) {
						res += dist[i];
					}
					//cout << "first type " << i << endl;
				}
				//cout << res << endl;
				for(int i = endofb(bnum(r) - 1); i < r; ++i) {
					if(last[i] >= l) {
						res += dist[i];
					}
					//cout << "second type " << i << endl;
				}
				//cout << res << endl;
				for(int i = bnum(l) + 1; i <= bnum(r) - 1; ++i) {
					int sar = startofb(i), tah = endofb(i);
					int aval = lower_bound(arr + sar, arr + tah, make_pair(l, -1)) - (arr + sar);
					if(aval == 0) {
						res += pdist[tah - 1];
					}
					else {
						res += pdist[tah - 1] - pdist[sar + aval - 1];
					}
					//cout << "third type " << i << ' ' << sar << ' ' << tah << ' ' << aval << "(( " << tah - 1 << ' ' << sar + aval - 1 << endl;
				}
				cout << res << endl;
			}
		}
  }
  return 0;
}

		  		 		 			 	 	  			  		 			