I won't feel lonely, nor will I be sorrowful... not before everything is buried.

A string of n beads is left as the message of leaving. The beads are numbered from 1 to n from left to right, each having a shape numbered by integers between 1 and n inclusive. Some beads may have the same shapes.

The memory of a shape x in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape x appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.

From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

Input

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 100 000) — the number of beads in the string, and the total number of changes and queries, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — the initial shapes of beads 1, 2, ..., n, respectively.

The following m lines each describes either a change in the beads or a query of subsegment. A line has one of the following formats: 

  * 1 p x (1 ≤ p ≤ n, 1 ≤ x ≤ n), meaning that the shape of the p-th bead is changed into x; 
  * 2 l r (1 ≤ l ≤ r ≤ n), denoting a query of memory of the subsegment from l to r, inclusive. 

Output

For each query, print one line with an integer — the memory of the recalled subsegment.

Examples

Input

7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7


Output

5
0
7
1


Input

7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7


Output

0
0

Note

The initial string of beads has shapes (1, 2, 3, 1, 3, 2, 1).

Consider the changes and queries in their order: 

  1. 2 3 7: the memory of the subsegment [3, 7] is (7 - 4) + (6 - 6) + (5 - 3) = 5; 
  2. 2 1 3: the memory of the subsegment [1, 3] is (1 - 1) + (2 - 2) + (3 - 3) = 0; 
  3. 1 7 2: the shape of the 7-th bead changes into 2. Beads now have shapes (1, 2, 3, 1, 3, 2, 2) respectively; 
  4. 1 3 2: the shape of the 3-rd bead changes into 2. Beads now have shapes (1, 2, 2, 1, 3, 2, 2) respectively; 
  5. 2 1 6: the memory of the subsegment [1, 6] is (4 - 1) + (6 - 2) + (5 - 5) = 7; 
  6. 2 5 7: the memory of the subsegment [5, 7] is (7 - 6) + (5 - 5) = 1. 
import java.io.*;
import java.util.*;

public class C {

	static final int QUERIES = 900000;

	int[] qx = new int[QUERIES];
	int[] qy = new int[QUERIES];
	int[] qd = new int[QUERIES];
	int qPtr = 0;

	void addModify(int x, int y, int d) {
		qx[qPtr] = x;
		qy[qPtr] = y;
		qd[qPtr] = d;
		qPtr++;
	}

	void addQuery(int x, int y) {
		qx[qPtr] = x;
		qy[qPtr] = y;
		qd[qPtr] = Integer.MAX_VALUE;
		qPtr++;
	}

	TreeSet<Integer>[] set;

	int n;

	void submit() {
		n = nextInt();
		int q = nextInt();

		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt() - 1;
		}

		int[] last = new int[n];
		Arrays.fill(last, -1);

		set = new TreeSet[n];
		for (int i = 0; i < n; i++) {
			set[i] = new TreeSet<>();
		}

		for (int i = 0; i < n; i++) {
			int x = a[i];
			if (last[x] != -1) {
				addModify(last[x], i, i - last[x]);
			}
			last[x] = i;
			set[x].add(i);
		}

		while (q-- > 0) {
			int type = nextInt();
			if (type == 1) {
				int pos = nextInt() - 1;
				int newVal = nextInt() - 1;

				modify(pos, a[pos], -1);

				a[pos] = newVal;
				modify(pos, a[pos], 1);
			} else {
				int l = nextInt() - 1;
				int r = nextInt() - 1;
				addQuery(l, r);
			}
		}

		// goStupid();
		goSmart();
	}
	
	static void addFen(long[] fen, int idx, int delta) {
		for (int i = idx; i < fen.length; i |= i + 1) {
			fen[i] += delta;
		}
	}
	
	static long getFen(long[] fen, int idx) {
		long ret = 0;
		for (int i = idx; i >= 0; i = (i & (i + 1)) - 1) {
			ret += fen[i];
		}
		return ret;
	}

	static class Node {
		int l, r;
		Node left, right;

		ArrayList<Integer> allY = new ArrayList<>();
		int[] uniqueY;
		long[] fen;

		public Node(int l, int r) {
			this.l = l;
			this.r = r;

			if (r - l > 1) {
				int m = (l + r) >> 1;
				left = new Node(l, m);
				right = new Node(m, r);
			}
		}

		void mark(int x, int y) {
			if (l >= x) {
				allY.add(y);
				return;
			}
			if (r <= x) {
				return;
			}
			left.mark(x, y);
			right.mark(x, y);
		}

		void makeUnique() {
			makeUniqueHere();
			if (r - l > 1) {
				left.makeUnique();
				right.makeUnique();
			}
		}
		
		void add(int x, int y, int d) {
			int idx = Arrays.binarySearch(uniqueY, y);
			if (idx < 0) {
				idx = -idx - 1;
			}
			if (idx < fen.length) {
				addFen(fen, idx, d);
			}
			if (r - l > 1) {
				(x < left.r ? left : right).add(x, y, d);
			}
		}
		
		long getSum(int x, int y) {
			if (l >= x) {
				int idx = Arrays.binarySearch(uniqueY, y);
				return getFen(fen, idx);
			}
			if (r <= x) {
				return 0;
			}
			return left.getSum(x, y) + right.getSum(x, y);
		}

		void makeUniqueHere() {
			if (allY.isEmpty()) {
				uniqueY = new int[0];
				fen = new long[0];
			} else {
				Collections.sort(allY);
				int sz = 1;
				for (int i = 1; i < allY.size(); i++) {
					if (!allY.get(i).equals(allY.get(sz - 1))) {
						allY.set(sz, allY.get(i));
						sz++;
					}
				}

				uniqueY = new int[sz];
				fen = new long[sz];
				for (int i = 0; i < sz; i++) {
					uniqueY[i] = allY.get(i);
				}
			}
			allY = null;
		}
	}

	void goSmart() {
		Node root = new Node(0, n);
		for (int i = 0; i < qPtr; i++) {
			int x = qx[i];
			int y = qy[i];
			int d = qd[i];

			if (d == Integer.MAX_VALUE) {
				root.mark(x, y);
			}
		}

		root.makeUnique();
		
		for (int i = 0; i < qPtr; i++) {
			int x = qx[i];
			int y = qy[i];
			int d = qd[i];
			if (d == Integer.MAX_VALUE) {
				out.println(root.getSum(x, y));
			} else {
				root.add(x, y, d);
			}
		}
		
	}

	void goStupid() {
		int[][] arr = new int[n][n];
		for (int i = 0; i < qPtr; i++) {
			int x = qx[i];
			int y = qy[i];
			int d = qd[i];

			if (d == Integer.MAX_VALUE) {

				int ret = 0;

				for (int ix = x; ix < n; ix++) {
					for (int iy = 0; iy <= y; iy++) {
						ret += arr[ix][iy];
					}
				}

				out.println(ret);
			} else {
				arr[x][y] += d;
			}
		}
	}

	void modify(int pos, int val, int sign) {

		if (sign == 1) {
			set[val].add(pos);
		} else {
			set[val].remove(pos);
		}

		Integer prev = set[val].lower(pos);
		Integer next = set[val].higher(pos);

		if (prev != null) {
			addModify(prev, pos, sign * (pos - prev));
		}
		if (next != null) {
			addModify(pos, next, sign * (next - pos));
		}
		if (prev != null && next != null) {
			addModify(prev, next, -sign * (next - prev));
		}
	}

	void preCalc() {

	}

	void stress() {

	}

	void test() {

	}

	C() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		preCalc();
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new C();
	}

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	int nextInt() {
		return Integer.parseInt(nextToken());
	}

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}
}
