#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
const int maxn=5e5+10;
struct node{
	int x,y;
}c[maxn];
int n,a[maxn],b[maxn],q,ans[maxn],stk[maxn],top;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main(){
//	freopen("stack.in","r",stdin);
//	freopen("stack.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(register int i=1;i<=n;i++) a[i]=read();
	for(register int i=1;i<=n;i++){
		b[i]=read();
		c[i].x=a[i],c[i].y=b[i];
	}
	for(register int i=1;i<=n;i++){
		while(top&&(c[stk[top]].x==c[i].x||c[stk[top]].y<=c[i].y)){
			ans[stk[top]]=i;
			--top;
		}
		stk[++top]=i;
	}
	//for(int i=1;i<=n;i++) printf("ans[%d]=%d\n",i,ans[i]);
	for(register int i=1;i<=q;i++){
		int l,r,anss=1;
		l=read();r=read();
		for(register int j=ans[l];j&&j<=r;j=ans[j]){
			anss++;
		}
		printf("%d\n",anss);
	}
	return 0;
}
/*
10 4
3 1 3 1 2 3 3 2 1 1
10 10 2 9 7 5 4 7 6 1
1 4
7 8
7 10
1 8
*/

评测记录