#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5005;
template<class comp> struct sparse_table{
	static comp _c;
	int st[21][N];
	void init(int n,int* a){
		for(int i=1;i<=n;i++) st[0][i]=a[i];
		for(int j=1;j<=20;j++){
			auto F=st[j],G=st[j-1];
			for(int i=1;i<=n-(1<<j)+1;i++){
				F[i]=min(G[i],G[i+(1<<j>>1)],_c);
			}
		}
	}
	int q(int l,int r){
		int len=__lg(r-l+1);
		return min(st[len][l],st[len][r-(1<<len)+1],_c);
	}
};
sparse_table<less<int>> Tmin;
sparse_table<greater<int>> Tmax;
int n,m;
int a[N],b[N];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	while(m--){
		int l,r;
		cin>>l>>r;
		int ans=0;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i]==a[j]&&Tmin.q(i,j)>=l&&Tmax.q(i,j)<=r) ans++;
		cout<<ans<<'\n';
	}
}