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
//Created by Aminul on 8/2/2020.

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(), q = in.nextInt();
        int arr[] = new int[n + 1];
        int last[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int x = in.nextInt();
            arr[i] = last[x];
            last[x] = i;
        }

        ArrayDeque<int[]> queries[] = genDQ(n + 1);
        for (int i = 0; i < q; i++) {
            int l = in.nextInt(), r = in.nextInt();

            queries[r].add(new int[]{i, l, +1});
            queries[l - 1].add(new int[]{i, l, -1});
        }

        BinaryIndexTree bit = new BinaryIndexTree(n + 10);
        int[] res = new int[q];
        for (int i = 1; i <= n; i++) {
            bit.add(arr[i], +1);
            for (int qry[] : queries[i]) {
                res[qry[0]] += qry[2] * bit.sum(qry[1] - 1);
            }
        }

        for (int ans : res) {
            pw.println(ans);
        }

        pw.close();
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static <T> ArrayDeque<T>[] genDQ(int n) {
        ArrayDeque<T> list[] = new ArrayDeque[n];
        for (int i = 0; i < n; i++) list[i] = new ArrayDeque<T>();
        return list;
    }

    static class BinaryIndexTree {
        public int bit[], n, offset = 5;

        public BinaryIndexTree(int N) {
            n = N;
            bit = new int[n + offset + 10];
        }

        public void add(int index, int value) {
            index += offset;
            for (; index < n; index = index + (index & -index)) {
                bit[index] += value;
            }
        }

        public int sum(int index) {
            index += offset;
            int sum = 0;
            for (; index > 0; index = index - (index & -index)) {
                sum += bit[index];
            }
            return sum;
        }

        public int query(int i, int j) {
            return sum(j) - sum(i - 1);
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() throws Exception {
            while (tokenizer == null || !tokenizer.hasMoreTokens())
                tokenizer = new StringTokenizer(reader.readLine());
            return tokenizer.nextToken();
        }

        public int nextInt() throws Exception {
            return Integer.parseInt(next());
        }

    }
}