#include<unistd.h>
char OB[65536]; int OP;
inline char RC(){static char buf[65536],*p=buf,*q=buf;return p==q&&(q=(p=buf)+read(0,buf,65536))==buf?-1:*p++;}
inline int R(){static char c;int a;while((c=RC())<'0');a=c^'0';while((c=RC())>='0')a*=10,a+=c^'0';return a;}
inline void W(int n){static char buf[12],p;if(n==0)OB[OP++]='0';p=0;while(n)buf[p++]='0'+(n%10),n/=10;for(--p;p>=0;--p)OB[OP++]=buf[p];OB[OP++]='\n';if(OP>65516)write(1,OB,OP),OP=0;}

#include<cstring>
#include<algorithm>
using namespace std;

#define FOR(i,n) for(int i = 0; i < n; ++i)
#define FOO(i,a,b) for(int i = a; i <= b; ++i)

const int N = 1<<18;
int n, m, a[N], id[N], ans[N], l[N], r[N];

struct segtree{
    int val[N<<1];
    void init(){
        memset(val, -1, sizeof(val));
    }
    // void modify(int p, int v){
    //  val[p += n] = v;
    //  for(; p > 0; p >>= 1)
    //      val[p>>1] = min(val[p], val[p^1]);
    // }
    // int query(int v){
    //  return query(v, 1, 0, N);
    // }
    void modify(int p, int v){
        val[p] = v;
    }
    int query(int v){
        int ans = 0;
        while(val[ans] >= v) ++ans;
        return ans;
    }
} sgt;

int main(){
    n = R(), m = R();
    FOO(i,1,n) a[i] = R();
    FOR(i,m) l[i] = R(), r[i] = R(), id[i] = i;
    sort(id, id + m, [](int a, int b){ return r[a] < r[b];});
    sgt.init();
    int cur = 0;
    FOR(i,m){
        while(cur < r[id[i]]) sgt.modify(a[++cur], cur);
        ans[id[i]] = sgt.query(l[id[i]]);
    }
    FOR(i,m) W(ans[i]);
    write(1,OB,OP);
    return 0;
}