// NOIP2022 RP++

#include <bits/stdc++.h>
typedef unsigned uint;
typedef unsigned long long ullt;typedef long long llt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
namespace RAB
{
    inline uint lowbit(uint v){return v&-v;}
    namespace Seg{
        ullt Val[1u<<20|1],Tag[1u<<20|1];
        voi add(uint p,uint l,uint r,ullt v,uint n){
            if(l>=r)return;
            Val[p]+=v*(r-l);
            if(!l&&r==n){Tag[p]+=v;return;}
            if(l<(n>>1))
                if(r<=(n>>1))add(p<<1,l,r,v,n>>1);
                else add(p<<1,l,n>>1,v,n>>1),add(p<<1|1,0,r-(n>>1),v,n>>1);
            else add(p<<1|1,l-(n>>1),r-(n>>1),v,n>>1);
        }
        ullt find(uint p,uint l,uint r,uint n){
            if(l>=r)return 0;
            if(!l&&r==n)return Val[p];
            if(l<(n>>1))
                if(r<=(n>>1))return find(p<<1,l,r,n>>1)+(r-l)*Tag[p];
                else return find(p<<1,l,n>>1,n>>1)+find(p<<1|1,0,r-(n>>1),n>>1)+(r-l)*Tag[p];
            else return find(p<<1|1,l-(n>>1),r-(n>>1),n>>1)+(r-l)*Tag[p];
        }
    };
    uint A[250005],B[250005];
    typedef std::pair<uint,uint>Pair;
    std::vector<Pair>Amax,Bmax;
    uint L[250005],R[250005];
    ullt Ans[250005];
    std::vector<uint>Q[250005];
    voi run(){
        uint n,q;scanf("%u",&n);
        for(uint i=0;i<n;i++)scanf("%u",A+i);
        for(uint i=0;i<n;i++)scanf("%u",B+i);
        scanf("%u",&q);
        for(uint i=0;i<q;i++)scanf("%u%u",L+i,R+i),L[i]--,Q[R[i]].push_back(i);
        uint qwq=1;while(qwq<n)qwq<<=1;
        for(uint i=0;i<n;i++){
            uint cnt1=1,cnt2=1;
            while(Amax.size()&&Amax.back().first<A[i])
                cnt1+=Amax.back().second,Amax.pop_back();
            while(Bmax.size()&&Bmax.back().first<B[i])
                cnt2+=Bmax.back().second,Bmax.pop_back();
            Amax.push_back({A[i],cnt1});
            Bmax.push_back({B[i],cnt2});
            for(uint i=0,j=0,p=0,q=0,l=0;i<Amax.size()&&j<Bmax.size();)
            {
                uint t=std::min(Amax[i].second-p,Bmax[j].second-q);
                Seg::add(1,l,l+t,(ullt)Amax[i].first*Bmax[j].first,qwq);
                l+=t,p+=t,q+=t;
                if(p==Amax[i].second)i++,p=0;
                if(q==Bmax[j].second)j++,q=0;
            }
            for(auto q:Q[i+1])
                Ans[q]=Seg::find(1,L[q],R[q],qwq);
        }
        for(uint i=0;i<q;i++)printf("%llu\n",Ans[i]);
    }
}

int main(){
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#else
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
#endif
    uint t;
    scanf("%u",&t);
    if((t>=1&&t<=9)||(t>=14&&t<=21)){
        RAB::run();
        return 0;
    }
    RAB::run();
    return 0;
}

/*
g++ match.cpp -o match -DMYEE -Wall -std=c++11
biu#2019miss
solo@2022
*/
