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

class Main{
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        st  = new StringTokenizer(br.readLine());

        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Query[] queries = new Query[q];
        ArrayList<Query>[] queriesAt = new ArrayList[n];
        for (int i=0; i<n; i++) queriesAt[i]=new ArrayList<>();

        for (int i=0; i<q; i++) {
            st  = new StringTokenizer(br.readLine());
            int l=Integer.parseInt(st.nextToken())-1;
            int r=Integer.parseInt(st.nextToken())-1;
            queries[i] = new Query(l,r,i);
            queriesAt[r].add(queries[i]);
        }

        int[] lastseen = new int[500001];
        Arrays.fill(lastseen, -1);

        SegTree segTree = new SegTree(0,n-1);

        for (int i=0; i<n; i++) {
            if (lastseen[arr[i]]!=-1) {
                segTree.update(lastseen[arr[i]],0);
            }
            lastseen[arr[i]] = i;
            segTree.update(lastseen[arr[i]],1);
            for (Query qq: queriesAt[i]){
                qq.ans = segTree.query(qq.l,qq.r);
            }
        }

        for (int i=0; i<q; i++) {
            out.println(queries[i].ans);
        }
        out.close();
    }

    static class SegTree{
        int leftmost,rightmost,sum;
        SegTree lchild, rchild;
        SegTree(int l, int r){
            leftmost=l;
            rightmost=r;
            if (leftmost==rightmost) {
                sum=0;
            }
            else {
                int mid = l+(r-l)/2;
                lchild = new SegTree(l, mid);
                rchild = new SegTree(mid+1, r);
            }
        }
        public void recalc() {
            if (leftmost!=rightmost) {
                sum = lchild.sum+rchild.sum;
            }
        }
        public void update(int idx, int val){
            if (leftmost==rightmost) {
                this.sum=val;
            }
            else if (idx<=lchild.rightmost) {
                lchild.update(idx, val);
            }
            else{
                rchild.update(idx, val);
            }
            recalc();
        }
        public int query(int l, int r){
            if (l>rightmost || r<leftmost) {
                return 0;
            }
            else if (l<=leftmost && r>=rightmost)
                return sum;
            else
                return lchild.query(l,r)+rchild.query(l,r);
        }
    }
    static class Query{
        int l,r,ans,idx;
        Query(int a, int b, int c){
            l=a;
            r=b;
            idx=c;
        }
    }




}