#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N=1e5+20;
const int inf=1e8+1e8+1e8+1e8+1e8*6;
int n,q;
int a[N];
int st[N][30];
void init(){
for(int i=1;i<=n;i++) st[i][0]=a[i];
a[0]=inf;
a[n+1]=inf;
st[0][0]=inf;
st[n+1][0]=inf;
n++;
for(int i=1;i<=29;i++){
for(int j=1;j<=n&&(j+(1<<(i-1)))<=n;j++){
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int getmax(int L,int R){
int k=log2(R-L+1);
return max(st[L][k],st[R-(1<<k)+1][k]);
}
int Lcheck(int x,int y){
int m=getmax(y,x-1);
int l=x+1,r=n,mid=0;
int pos=0;
while(l<=r){
mid=(l+r)>>1;
if(getmax(x+1,mid)<m){
pos=mid;
l=mid+1;
}else r=mid-1;
}
if(pos==0) return x-y+1;
return pos-x+1+x-y;
}
int Rcheck(int x,int y){
int m=getmax(x+1,y);
int l=0,r=x-1,mid=0;
int pos=0;
while(l<=r){
mid=(l+r)>>1;
if(getmax(mid,x-1)<m){
pos=mid;
r=mid-1;
}else l=mid+1;
}
if(pos==0) return y-x+1;
return x-pos+1+y-x;
}
int query(int p,int k){
if(k==1) return 1;
int pos=0,pos2=0,t1=0;
int l,r,mid;
if(p-k>=0){
l=p-k,r=p-1,mid=0;
while(l<=r){
mid=(l+r)>>1;
if(Rcheck(mid,p)>k){
l=mid+1;
pos=mid;
}else r=mid-1;
}
l=p-k+1,r=p-1;
while(l<=r){
mid=(l+r)>>1;
if(Rcheck(mid,p)>=k){
l=mid+1;
pos2=mid;
}else r=mid-1;
}
}
t1=max(0,pos2-pos);
l=p+1,r=p+k,mid=0;
pos=pos2=0;
if(p+k<=n){
while(l<=r){
mid=(r+l)>>1;
if(Lcheck(mid,p)>k){
r=mid-1;
pos=mid;
}else l=mid+1;
}
l=p+1,r=p+k-1;
while(l<=r){
mid=(l+r)>>1;
if(Lcheck(mid,p)>=k){
r=mid-1;
pos2=mid;
}else l=mid+1;
}
}
return max(0,pos-pos2)+t1;
}
int main(){
n=read();
q=read();
for(int i=1;i<=n;i++) a[i]=read();
init();
while(q--){
int x=read();
int y=read();
printf("%d\n",query(x,y));
}
return 0;
}