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

// https://atcoder.jp/contests/abc174/submissions/15644479 のテスト
public class Main {
	public static void main (String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] first = br.readLine().split(" ", 2);
 		int n = Integer.parseInt(first[0]);
		int q = Integer.parseInt(first[1]);
		String[] nums = br.readLine().split(" ", n);
		Query[] queries = new Query[q];
		for (int i = 0; i < q; i++) {
		    String[] line = br.readLine().split(" ", 2);
		    queries[i] = new Query(i, Integer.parseInt(line[0]), Integer.parseInt(line[1]));
		}
		Arrays.sort(queries);
		int[] idxes = new int[n + 1];
		BinaryIndexedTree bit = new BinaryIndexedTree(n + 1);
		int[] ans = new int[q];
		int idx = 0;
		for (int i = 0; i < n; i++) {
		    int y = Integer.parseInt(nums[i]);
		    if (idxes[y] > 0) {
		        bit.add(idxes[y], - 1);
		    }
		    bit.add(i + 1, 1);
		    idxes[y] = i + 1;
		    while (idx < q && queries[idx].right == i + 1) {
		        ans[queries[idx].idx] = bit.getSum(queries[idx].left, queries[idx].right);
		        idx++;
		    }
		}
		StringBuilder sb = new StringBuilder();
		for (int x : ans) {
		    sb.append(x).append("\n");
		}
		System.out.print(sb);
	}
	
	static class Query implements Comparable<Query> {
	    int idx;
	    int left;
	    int right;
	    
	    public Query(int idx, int left, int right) {
	        this.idx = idx;
	        this.left = left;
	        this.right = right;
	    }
	    
	    public int compareTo(Query another) {
	        return right - another.right;
	    }
	}
}
 
class BinaryIndexedTree {
    int size;
    int[] tree;
    
    public BinaryIndexedTree(int size) {
        this.size = size;
        tree = new int[size];
    }
    
    public void add(int idx, int value) {
        int mask = 1;
        while (idx < size) {
            if ((idx & mask) != 0) {
                tree[idx] += value;
                idx += mask;
            }
            mask <<= 1;
        }
    }
    
    public int getSum(int from, int to) {
        return getSum(to) - getSum(from - 1);
    }
    
    public int getSum(int x) {
        int mask = 1;
        int ans = 0;
        while (x > 0) {
            if ((x & mask) != 0) {
                ans += tree[x];
                x -= mask;
            }
            mask <<= 1;
        }
        return ans;
    }
}