import java.util.*;
import java.io.*;
/*
7 1
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6

 */
public class e
{
	public static void main(String[] arg) throws IOException
	{
		new e();
	}
	final int SQRT = 317;
	int n;
	int[] vs;
	TreeSet<Integer>[] ts;
	Pair[] buckets;
	Pair[] temp;
	public e() throws IOException
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		n = in.nextInt();
		temp = new Pair[SQRT];
		for(int i = 0; i < SQRT; i++) temp[i] = new Pair();
		int m = in.nextInt();
		vs = new int[n];
		for(int i = 0; i < n; i++) vs[i] = in.nextInt();
		ts = new TreeSet[n+1];
		for(int i = 0; i <= n; i++)
		{
			ts[i] = new TreeSet<Integer>();
			ts[i].add(n);
		}
		for(int i = 0; i < n; i++) {
			ts[vs[i]].add(i);
		}
		buckets = new Pair[n];
		for(int i = 0; i < n; i++) buckets[i] = new Pair();
		for(int i = 0; i < buckets.length; i+=SQRT) {
			construct(i);
		}
		for(int ii = 0; ii < m; ii++) {
			int queryType = in.nextInt();
			if(queryType == 1) {
				int p = in.nextInt()-1;
				int x = in.nextInt();
				ts[vs[p]].remove(p);
				Integer prev = ts[vs[p]].lower(p);
				if(prev != null) {
					construct(prev/SQRT);
				}
				vs[p] = x;
				ts[vs[p]].add(p);
				prev = ts[vs[p]].lower(p);
				if(prev != null) {
					construct(prev/SQRT);
				}
				construct(p/SQRT);
			} else {
				int lq = in.nextInt()-1;
				int rq = in.nextInt()-1;
				long sum = 0;
				for(int li = 0; li < n; li+=SQRT) {
					int ri = li+SQRT-1;
					if(rq < li || ri < lq) continue;
					if(lq <= li && ri <= rq) {
						sum += bs(li, ri, lq, rq);
					} else {
						for(int j = li; j <= ri; j++) {
							if(lq <= j && j <= rq) {
								Integer next = ts[vs[j]].higher(j);
								if(next != null && lq <= next && next <= rq) {
									sum += next-j;
								}
							}
						}
					}
				}
				out.println(sum);
			}
		}
		in.close(); out.close();
	}
	long bs(int low, int high, int lq, int rq) {
		while(low <= high) {
			int mid = low+(high-low)/2;
			if(buckets[mid].next > rq) high = mid-1;
			else low = mid+1;
		}
		if(0 <= high && lq <= buckets[high].next && buckets[high].next <= rq) return buckets[high].delta;
		return 0;
	}
	void construct(int startIdx) {
		int endIdx = Math.min(startIdx+SQRT, n);
		for(int i = startIdx; i < endIdx; i++) {
			Integer next = ts[vs[i]].higher(i);
			temp[i-startIdx].set(next, next-i);
		}
		for(int i = endIdx; i < temp.length; i++)
		{
			temp[i-startIdx].set(n+1, n+1);;
		}
		Arrays.sort(temp);
		for(int i = startIdx; i < endIdx; i++) {
			buckets[i] = temp[i-startIdx];
			if(i != startIdx) buckets[i].delta += buckets[i-1].delta;
		}
	}
	class Pair implements Comparable<Pair> {
		int next; 
		long delta;
		
		public void set(int a, long b) {
			next = a;
			delta = b;
		}
		public int compareTo(Pair p) {
			return Integer.compare(next, p.next);
		}
		public String toString() {
			return next + " " + delta;
		}
	}
	class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(InputStream in)
		{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		public String next() throws IOException {
			while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public void close() throws IOException {
			br.close();
		}
	}
}
