We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

* 1\leq N,Q \leq 5 \times 10^5
* 1\leq c_i \leq N
* 1\leq l_i \leq r_i \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the response to the i-th query.

Examples

Input

4 3
1 2 1 3
1 3
2 4
3 3


Output

2
3
1


Input

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8


Output

1
2
2
1
2
2
6
3
3
3
import java.io.*;
import java.math.*;
import java.util.*;
 
public class Main {
	static final long MOD = 1000000007L;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = sc.ni();
		int Q = sc.ni();
		int M = 500000;
		int[] nums = new int[N];
		ArrayDeque<Integer>[] indices = new ArrayDeque[M];
		for (int i = 0; i < N; i++) {
			nums[i] = sc.ni()-1;
			if (indices[nums[i]]==null) {
				indices[nums[i]] = new ArrayDeque<Integer>();
			}
			indices[nums[i]].add(i);
		}
		int[][] queries = new int[Q][3];
		for (int q = 0; q < Q; q++) {
			queries[q][0] = sc.ni()-1;
			queries[q][1] = sc.ni()-1;
			queries[q][2] = q;
		}
		queries = sort(queries);
		
		int[] cur = new int[M];
		Arrays.fill(cur,-1); //cur last index of element i.
		BinaryIndexedTree bit = new BinaryIndexedTree(N);
		for (int i = 0; i < M; i++) {
			if (indices[i]!=null) {
				int index = indices[i].pollFirst();
				if (indices[i].isEmpty())
					indices[i] = null;
				cur[i] = index;
				bit.add(1, cur[i]);
			}
		}
		int[] ans = new int[Q];
		int L = 0;
		for (int[] query: queries) {
			while (L < query[0]) {
				int num = nums[L];
				int last = cur[num];
				bit.add(-1, last);
				L++;
				if (indices[num] != null) {
					int next = indices[num].pollFirst();
					if (indices[num].isEmpty())
						indices[num] = null;
					bit.add(1, next);
					cur[num] = next;
				}

			}
			ans[query[2]] = bit.sum(query[0], query[1]+1);
		}
		for (int a: ans)
			pw.println(a);
		
		pw.close();
	}
	
	//0 indexed
	static class BinaryIndexedTree {
		public int[] arr;

		public BinaryIndexedTree (int N) {
			arr = new int[N+1];
		}

		//add k to the i-th element.
		public void add(int k, int i) {
			int node = i+1;
			while (node < arr.length) {
				arr[node] += k;
				node += node & (-node);
			}
		}

		//sum up the elements from input[s_i] to input[e_i], from [s_i,e_i).
		public int sum(int s_i, int e_i) {
			return sum(e_i) - sum(s_i);
		}

		public int sum(int i) {
			int total = 0;
			int node = i;
			while (node > 0) {
				total += arr[node];
				node -= node & (-node);
			}
			return total;
		}
	}
	
	public static int[][] sort(int[][] arr) {
		//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < arr.length; i++) {
			int randomPosition = rgen.nextInt(arr.length);
			int[] temp = arr[i];
			arr[i] = arr[randomPosition];
			arr[randomPosition] = temp;
		}
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] arr1, int[] arr2) {
				return arr1[0]-arr2[0];
				//Ascending order.
			}
		});
		return arr;
	}
	
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }
        
        int ni() { 
            return Integer.parseInt(next()); 
        }
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() {
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}