RT

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll MAXN=2.5e5;
ll n,q;
ll a[MAXN],b[MAXN];
ll st_a[MAXN],st_b[MAXN],top_a,top_b;
struct node{
	ll l,r,id;
	bool operator < (const node &oth)const{
		return r<oth.r;
	}
}t[MAXN];
struct sgm_t{
	ll sum_x,sum_y,sum_xy,sum_s;
	sgm_t():sum_x(0),sum_y(0),sum_xy(0),sum_s(0){}
	sgm_t(ll SX,ll SY,ll SXY,ll SS):sum_x(SX),sum_y(SY),sum_xy(SXY),sum_s(SS){}
	sgm_t operator + (const sgm_t &oth)const{
		return sgm_t(sum_x+oth.sum_x,sum_y+oth.sum_y,sum_xy+oth.sum_xy,sum_s+oth.sum_s);
	}
};
struct Tag{
	ll add_x,add_y,add_xy,add_c;
	ll set_x,set_y;
	Tag():add_x(0),add_y(0),add_xy(0),add_c(0),set_x(0),set_y(0){}
	Tag(ll AX,ll AY,ll AXY,ll AC,ll SX,ll SY):add_x(AX),add_y(AY),add_xy(AXY),add_c(AC),set_x(SX),set_y(SY){}
	operator bool() const{return add_x||add_y||add_xy||add_c||set_x||set_y;}
	Tag operator * (const Tag &oth)const{//oth<--tag 
		ll _ax=oth.add_x,_ay=oth.add_y,_axy=oth.add_xy,_ac=oth.add_c,_sx=oth.set_x,_sy=oth.set_y;
		if(_sx&&_sy)_ac+=add_xy*_sx*_sy+add_x*_sx+add_y*_sy;
		if(_sx&&!_sy){
			_ac+=add_x*_sx;
			_ay+=add_xy*_sx;
		}
		if(!_sx&&_sy){
			_ac+=add_x*_sy;
			_ax+=add_xy*_sy;
		}
		if(!_sx&&!_sy){
			_ax+=add_x;
			_ay+=add_y;
			_axy+=add_xy;
		}
		_ac+=add_c;
		if(set_x)_sx=set_x;
		if(set_y)_sy=set_y;
		return Tag(_ax,_ay,_axy,_ac,_sx,_sy);
	}
	sgm_t apply(sgm_t oth,ll len){
		return sgm_t(set_x?set_x*len:oth.sum_x,set_y?set_y*len:oth.sum_y,
		set_x?(set_y?set_x*set_y*len:set_x*oth.sum_y):(set_y?oth.sum_x*set_y:oth.sum_xy),
		oth.sum_s+add_xy*oth.sum_xy+add_x*oth.sum_x+add_y*oth.sum_y+add_c*len);
	}
};
sgm_t tree[MAXN<<2];
Tag tag[MAXN<<2];
void push_up(ll id){
	tree[id]=tree[id<<1]+tree[id<<1|1];
	return;
}
void add_tag(ll id,ll L,ll R,Tag T){
	tag[id]=T*tag[id];
	tree[id]=T.apply(tree[id],R-L+1);
	return;
}
void push_down(ll id,ll L,ll R){
	if(tag[id]){
		ll mid=(L+R)>>1;
		add_tag(id<<1,L,mid,tag[id]);
		add_tag(id<<1|1,mid+1,R,tag[id]);
		tag[id]=Tag();
	}
	return;
}
void update(ll id,ll L,ll R,ll UL,ll UR,Tag T){
	if(UL<=L&&R<=UR){
		add_tag(id,L,R,T);
		return;
	}
	push_down(id,L,R);
	ll mid=(L+R)>>1;
	if(UL<=mid)update(id<<1,L,mid,UL,UR,T);
	if(UR>mid)update(id<<1|1,mid+1,R,UL,UR,T);
	push_up(id);
	return;
}
ll query(ll id,ll L,ll R,ll QL,ll QR){
	if(QL>R||QR<L)return 0;
	if(QL<=L&&R<=QR)return tree[id].sum_s;
	push_down(id,L,R);
	ll mid=(L+R)>>1;
	return query(id<<1,L,mid,QL,QR)+query(id<<1|1,mid+1,R,QL,QR);
}
ll ans[MAXN];
int main(){
	cin>>n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	cin>>q;
	for(int i=1;i<=q;i++)cin>>t[i].l>>t[i].r;
	for(int i=1;i<=q;i++)t[i].id=i;
	sort(t+1,t+1+q);
	for(int i=1,j=1;i<=n;i++){
		while(top_a&&a[st_a[top_a]]<a[i])top_a--;
		while(top_b&&b[st_b[top_b]]<b[i])top_b--;
		update(1,1,n,st_a[top_a]+1,i,Tag(0,0,0,0,a[i],0));
		update(1,1,n,st_b[top_b]+1,i,Tag(0,0,0,0,0,b[i]));
		update(1,1,n,1,i,Tag(0,0,1,0,0,0));
		st_a[++top_a]=i;
		st_b[++top_b]=i;
		while(j<=q&&t[j].r==i){
			ans[t[j].id]=query(1,1,n,t[j].l,i);
			j++;
		}
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
	return 0;
}