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.util.*; 

class Main
{ 
    static class Foster 
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next() 
        {
            while (!st.hasMoreTokens())
                try 
                {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) 
                {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int nextInt() 
        {
            return Integer.parseInt(next());
        }
        long nextLong() 
        {
            return Long.parseLong(next());
        }
        double nextDouble() 
        {
            return Double.parseDouble(next());
        }
        int[] intArray(int n)                   // Check indices
        {
            int arr[] = new int[n];
            for(int i = 0; i < n; i++)
            {
                arr[i] = nextInt();
            }
            return arr;
        }
        long[] longArray(int n)                 // Check indices
        {
            long arr[] = new long[n];
            for(int i = 0; i < n; i++)
            {
                arr[i] = nextLong();
            }
            return arr;
        }
        int[] getBits(int n)                    //in Reverse Order
        {
            int a[] = new int[31];
            for(int i = 0; i < 31; i++)
            {
                if(((1<<i) & n) != 0)
                    a[i] = 1;
            }
            return a;
        }
        static long pow(long... a)
        {
            long mod = Long.MAX_VALUE;
            if(a.length == 3)   mod = a[2];
            long res = 1;
            while(a[1] > 0)
            {
                if((a[1] & 1) == 1)
                    res = (res * a[0]) % mod;
                a[1] /= 2;
                a[0] = (a[0] * a[0]) % mod;
            }
            return res;
        }
        void print(Object... o) 
        {
            for(Object next : o)
            {
                System.out.print(next + " ");
            }
        }
        void println(Object... o) 
        {
            for(Object next : o)
            {
                System.out.print(next + " ");
            }
            System.out.println();
        }
        void watch(Object...a) throws Exception 
        {
            int i = 1;
            for (Object o: a) 
            {
                boolean found = false;
                if (o.getClass().isArray()) 
                {
                    String type = o.getClass().getName().toString();
                    switch (type) 
                    {
                        case "[I":
                        {
                            int[] test = (int[]) o;
                            println(i + " : " + Arrays.toString(test));
                            break;
                        }
                        case "[[I":
                        {
                            int[][] obj = (int[][]) o;

                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[J":
                        {

                            long[] obj = (long[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[J":
                        {

                            long[][] obj = (long[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[D":
                        {

                            double[] obj = (double[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[D":
                        {

                            double[][] obj = (double[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[Ljava.lang.String":
                        {

                            String[] obj = (String[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[Ljava.lang.String":
                        {

                            String[][] obj = (String[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        case "[C":
                        {
                            char[] obj = (char[]) o;
                            println(i + " : " + Arrays.toString(obj));
                            break;
                        }
                        case "[[C":
                        {

                            char[][] obj = (char[][]) o;
                            println(i + " : " + Arrays.deepToString(obj));
                            break;
                        }
                        default:
                        {
                            println(i + " : type not identified");
                            break;
                        }
                    }
                    found = true;
                }
                if (o.getClass() == ArrayList.class) 
                {
                    println(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == TreeSet.class) 
                {
                    println(i + " : SET = " + o);
                    found = true;
                }
                if (o.getClass() == TreeMap.class) 
                {
                    println(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == HashMap.class) 
                {
                    println(i + " : MAP = " + o);
                    found = true;
                }
                if (o.getClass() == LinkedList.class) 
                {
                    println(i + " : LIST = " + o);
                    found = true;
                }
                if (o.getClass() == PriorityQueue.class) 
                {
                    println(i + " : PQ = " + o);
                    found = true;
                }
                if (!found) 
                {
                    println(i + " = " + o);
                }
                i++;
            }
        }
    }

	static int MAX = 1000001; 

	static class Query 
	{ 
		int l, r, idx; 
        public Query(int l, int r, int idx)
        {
            this.l = l;
            this.r = r;
            this.idx = idx;
        }
	} 

	static void update(int idx, int val, int bit[], int n) 
	{ 
		for (; idx <= n; idx += idx & -idx) 
			bit[idx] += val; 
	} 

	static int query(int idx, int bit[], int n) 
	{ 
		int sum = 0; 
		for (; idx > 0; idx -= idx & -idx) 
			sum += bit[idx]; 
		return sum; 
	} 
    static int[] ans;
	static void answeringQueries(int[] arr, int n, Query[] queries, int q) 
	{ 
		int[] bit = new int[n + 1]; 
		Arrays.fill(bit, 0); 
		int[] last_visit = new int[MAX]; 
		Arrays.fill(last_visit, -1); 

		int query_counter = 0; 
		for (int i = 0; i < n; i++) 
		{ 
			if (last_visit[arr[i]] != -1) 
				update(last_visit[arr[i]] + 1, -1, bit, n); 
			last_visit[arr[i]] = i; 
			update(i + 1, 1, bit, n); 

			while (query_counter < q && queries[query_counter].r == i) 
			{ 
				ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) - query(queries[query_counter].l, bit, n); 
				query_counter++; 
			} 
		} 
	} 

	// Driver Code 
	public static void main(String[] args) 
	{ 
        Foster sc = new Foster();
        PrintWriter p = new PrintWriter(System.out);
        int n = sc.nextInt(), q = sc.nextInt();
		int a[] = sc.intArray(n);
        ans = new int[q]; 
		Query[] queries = new Query[q]; 
		for (int i = 0; i < q; i++) 
        {
            int l = sc.nextInt(), r = sc.nextInt();
            l--;
            r--;
			queries[i] = new Query(l,r,i); 
        }
		Arrays.sort(queries, new Comparator<Query>() 
		{ 
			public int compare(Query x, Query y) 
			{ 
				if (x.r < y.r) 
					return -1; 
				else if (x.r == y.r) 
					return 0; 
				else
					return 1; 
			} 
		}); 
		answeringQueries(a, n, queries, q); 
        
		for (int i = 0; i < q; i++) 
			p.println(ans[i]); 
        p.close();
	} 
} 
