#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

FILE *fin=fopen("knjige.in", "r");
FILE *fout=fopen("knjige.out", "w");

struct T{
    int v, ind;
    bool operator<(const T &a) const{
        if (v==a.v) return ind<a.ind;
        return v<a.v;
    }
    T(){};
    T(int _v, int _ind){
        v=_v; ind=_ind;
    }
    void pisi(){
        printf("(%d,%d)\n", v,ind);
    }
};


int n, k, d;
int a[150000], b[150000];
int p[150000];
T t[150000];

void input(){
    fscanf(fin, "%d%d", &n, &k);
    for (int i=0; i<n; i++){
        int p;
        fscanf(fin, "%d", &p);
        t[i]=T(p, i+1);
    }
    for (int i=0; i<k; i++) fscanf(fin, "%d%d", a+i, b+i);
}

void solve1(){
    for (int i=0; i<k; i++){
        int sol=0;
        for (int j=0; j<d; j++){
            int left=p[j], right=p[j+1]-1;
            bool found=false;

            while (!found){
                int mid=(left+right)/2;
                if (t[mid].ind<a[i]) left=mid+1;
                    else if (t[mid].ind>b[i]) right=mid-1;
                        else {
                            sol++; found=true;
                        }
                if (left>right) found=true;
            }
        }
        fprintf(fout,"%d\n", sol);
    }
    fclose(fout);
    exit(0);
}

void solve2(){


}

void solve(){
    sort(t,t+n);
    p[0]=0;
    int i=1; d=1;
    while (i<n){
        while (i<n && t[i].v==t[i-1].v) i++;
        p[d]=i; d++; i++;
    }
    p[d]=i;
    if (t[n-1].v<=60) solve1();
    if (n<=1000 && k<=1000) solve1();

}



int main(){
    input();
    solve();


    return 0;
}
