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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static final FS sc = new FS();  // 封装输入类
    static final PrintWriter pw = new PrintWriter(System.out);
    static int[] t;
    static int n, q;
    public static void main(String[] args) {
        n = sc.nextInt();
        q = sc.nextInt();
        int[] colors = new int[n];
        int[] lastPos = new int[n];
        Arrays.fill(lastPos, -1);
        int[] next = new int[n];
        Arrays.fill(next, -1);
        t = new int[n];
        for (int i = 0; i < n; i++) {
            colors[i] = sc.nextInt() - 1;
            if (lastPos[colors[i]] != -1) {
                next[lastPos[colors[i]]] = i;
            } else {
                add(i, 1);
            }
            lastPos[colors[i]] = i;
        }
        Query[] queries = new Query[q];
        for (int i = 0; i < q; i++) {
            queries[i] = new Query(sc.nextInt() - 1, sc.nextInt() - 1, i);
        }
        Arrays.sort(queries, Comparator.comparingInt(o -> o.from));
        int curFr = 0;
        int[] res = new int[q];
        for (Query query : queries) {
            while (curFr != query.from) {
                int ne = next[curFr];
                if (ne != -1) {
                    add(ne, 1);
                }
                add(curFr, -1);
                curFr++;
            }
            res[query.id] = get(query.to);
        }
        for (int x : res) {
            pw.println(x);
        }
        pw.flush();
    }

    static void add(int pos, int x) {
        for (; pos < n; pos |= pos + 1) {
            t[pos] += x;
        }
    }

    static int get(int pos) {
        int r = 0;
        for (; pos >= 0; pos = (pos & (pos + 1)) - 1) {
            r += t[pos];
        }
        return r;
    }

    static class Query {
        int from, to, id;
        public Query(int from, int to, int id) {
            this.from = from;
            this.to = to;
            this.id = id;
        }
    }

    static class FS {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next() {
            while(!st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(Exception ignored) {}
            }
            return st.nextToken();
        }
        int[] nextArray(int n) {
            int[] a = new int[n];
            for(int i = 0;i < n;i++) {
                a[i] = nextInt();
            }
            return a;
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}