#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;

int n, q, a[N + 5], c[N + 5], f[N + 5]; 
stack<int> stk[N + 5];

int tot,rt[N];
struct node{
	int ls,rs,cnt;
}tr[32*N];

void insert(int& u,int v,int l,int r,int val){
	u=++tot;
	tr[u]=tr[v];
	tr[u].cnt++;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	if(val<=mid){
		insert(tr[u].ls,tr[v].ls,l,mid,val);
	}
	else{
		insert(tr[u].rs,tr[v].rs,mid+1,r,val);
	}
}
int query(int u,int v,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return tr[u].cnt-tr[v].cnt;
	}
	int mid=(l+r)>>1;
	if(y<=mid){
		return query(tr[u].ls,tr[v].ls,l,mid,x,y);
	}
	if(x>mid){
		return query(tr[u].rs,tr[v].rs,mid+1,r,x,y);
	}
	return query(tr[u].ls,tr[v].ls,l,mid,x,y)+query(tr[u].rs,tr[v].rs,mid+1,r,x,y);
}

int main () {
	scanf ("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]);
	for (int i = 1; i <= n; i ++) scanf ("%d", &c[i]);
	for (int i = 1; i <= n; i ++) {
		if (a[i] == 0) stk[c[i]].push(i);
		else if (a[i] == 1) {
			if (stk[c[i]].empty()) f[i] = 1;
			else {
				f[i] = stk[c[i]].top() + 1; 
				stk[c[i]].pop();
			}
		}
	}
	for (int i = 1; i <= n; i ++) insert(rt[i], rt[i - 1], 1, n + 1, f[i]);
	for (int l, r; q --; ) {
		scanf ("%d%d", &l, &r);
		printf("%d\n", query(rt[r], rt[l], 1, n + 1, l + 1, n + 1));
	}
	return 0;
}