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

public class Main{
    static PrintWriter out = new PrintWriter(System.out);
    long mod = 1000000000+7;
    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static public void main(String[] args) throws Exception{
        //BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //String[] buf = reader.readLine().split(" ")
        Main main = new Main();
        int t= 1;
        while(t-->0){
            main.solve();
        }
//        main.solve();
        out.flush();
    }
    void solve() throws Exception{
        //
        String[] buf = reader.readLine().split(" ");
        int n = parIn(buf[0]), q = parIn(buf[1]);
        int[] color = new int[n+1];
        buf = reader.readLine().split(" ");
        for(int i=1; i<=n; i++) color[i] = parIn(buf[i-1]);
        int[] bit = new int[n+1];
        int[][] qlr = new int[q][];

        for(int i=0; i<q; i++){
            buf = reader.readLine().split(" ");
            qlr[i] = new int[]{i, parIn(buf[0]), parIn(buf[1])};
        }
        Arrays.sort(qlr, Comparator.comparingInt(o1->o1[2])); // ascending order or r[i]
        int now = 1;
        int[] last = new int[n+1];
        int[] ans = new int[q];
        boolean[] seen = new boolean[n+1];
        int total = 0;
        for(int i=0; i<q; i++){
            int[] cur = qlr[i];
            while(now<=cur[2]){
                int c = color[now];
                if(!seen[c]) {
                    total += 1;
                    seen[c] = true;
                }
                if(last[c]>0){
                    addTo(last[c], -1, n, bit);
                }
                last[c] = now;
                addTo(now, 1, n, bit);
                now++;
            }
            int l = cur[1], r = cur[2];
            int temp = total-sum(l-1, n, bit);
            ans[cur[0]] = temp;
        }
        for(int i=0; i<q; i++) out.println(ans[i]);
    }
    void addTo(int idx, int val, int n, int[] bit){
        while(idx<=n){
            bit[idx] += val;
            idx += idx&(-idx);
        }
    }
    int sum(int idx, int n, int[] bit){
        int ans= 0;
        while(idx>0){
            ans += bit[idx];
            idx -= idx&(-idx);
        }
        return ans;
    }
    int parIn(String s){return Integer.parseInt(s);}
}

