/* Author haleyk10198 */
/* 作者:  haleyk10198 */
/* CF handle: haleyk100198*/
#include <bits/stdc++.h>

#define MOD 1000000007
#define LINF (1LL<<60)
#define INF 2147483647
#define PI 3.1415926535897932384626433
#define ll long long
#define pii pair<int,int>
#define mp(x,y) make_pair((x),(y))
#define pb(x) push_back((x))
#define vi vector<int>
#define vvi vector<vi>
#define SQN 317

using namespace std;

string itos(int x){
	stringstream ss;
	ss << x;
	return ss.str();
}

int n, m, a[100010], redT[100010], accT[100010];

set<int> s[100010];

void add(int pos, int v, int *T){
	for( ++pos; pos <= n; pos+=pos&-pos)
		T[pos] += v;
	return;
}

int ask(int pos, int *T){
	int ret = 0;
	for( ++pos; pos; pos-=pos&-pos)
		ret += T[pos];
	return ret;
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> a[i], s[a[i]].insert(i);
	for(int i = 1; i <= n; i++) s[i].insert(n);
	
	for(int i = 0; i < n; i++){
		auto it = s[a[i]].upper_bound(i);
		int nxt = *it;
		add(i, nxt-i, accT);
		add(i, nxt-i, redT);
		if(nxt == n)
			add(n, i-nxt, redT);
		if(--it != s[a[i]].begin()){
			--it;
			int prv = *it;
			add(i, prv-i, redT);
		}
	}
	
	for(int i = 0; i < m; i++){
		int op; cin >> op;
		if(op == 1){
			int pos, x; cin >> pos >> x;
			--pos;
			
			auto it = s[a[pos]].upper_bound(pos);
			int nxt = *it;
			add(pos, pos-nxt, accT);
			add(pos, pos-nxt, redT);
			add(nxt, nxt-pos, redT);
			--it;
			if(it-- != s[a[pos]].begin()){
				int prv = *it;
				add(prv, prv-pos, accT);
				add(prv, nxt-prv, accT);
				add(prv, nxt-prv, redT);
				add(nxt, prv-nxt, redT);
			}
			s[a[pos]].erase(pos);
			
			a[pos] = x;
			it = s[a[pos]].upper_bound(pos);
			nxt = *it;
			add(pos, nxt-pos, accT);
			add(pos, nxt-pos, redT);
			add(nxt, pos-nxt, redT);
			if(it != s[a[pos]].begin()){
				--it;
				int prv = *it;
				add(prv, prv-nxt, accT);
				add(prv, pos-prv, accT);
			
				add(prv, prv-nxt, redT);
				add(nxt, nxt-prv, redT);
				add(prv, pos-prv, redT);
				add(pos, prv-pos, redT);
			}
			s[a[pos]].insert(pos);
		}
		else{
			int l, r; cin >> l >> r; --l, --r;
			int res = ask(r, accT)-ask(l-1, accT);
			res -= ask(r, redT);
			cout << res << endl;
		}
	}
	return 0;
}