#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
#define ull unsigned long long
int n;
inline int read()
{
	char C=getchar();
	int ANS=0,F=1;
	while (C<'0'||C>'9')
	{
		if (C=='-') F=-1;
		C=getchar();
	}
	while (C>='0'&&C<='9')
	{
		ANS=ANS*10+(C-'0');
		C=getchar();
	}
	return ANS*F;
}
namespace sub1
{
	const int N=3005;
	int sa[N][N],sb[N][N];
	ull sum[N][N];
	void work()
	{
		ull it=1;
		n=read();
		for (int i=1;i<=n;i++) sa[i][i]=read();
		for (int i=1;i<=n;i++) sb[i][i]=read();
		for (int l=1;l<n;l++)
		{
			for (int i=1;i+l<=n;i++)
			{
				int j=i+l;
				sa[i][j]=max(sa[i][j-1],sa[j][j]);
				sb[i][j]=max(sb[i][j-1],sb[j][j]);
			}
		}
		for (int i=1;i<=n;i++) sum[i][i]=it*sa[i][i]*sb[i][i];
		for (int l=1;l<n;l++)
		{
			for (int i=1;i+l<=n;i++)
			{
				int j=i+l;
				sum[i][j]=sum[i+1][j]+sum[i][j-1]-sum[i+1][j-1]+it*sa[i][j]*sb[i][j];
			}
		}
		int q=read();
		while (q--)
		{
			int l=read(),r=read();
			cout << sum[l][r] << endl;
		}
	}
}
namespace sub2
{
	const int N=300005;
	__gnu_pbds::gp_hash_table<ull,ull>qa,qb;
	int a[N],b[N];
	int fa[N][21],fb[N][21];
	int pa[N],pb[N];
	void STwork()
	{
		int t=__lg(n);
		for (int i=1;i<=n;i++) fa[i][0]=a[i],fb[i][0]=b[i];
		for (int i=1;i<=t;i++)
		{
			for (int j=1;j+(1<<i)-1<=n;j++)
			{
				fa[j][i]=max(fa[j][i-1],fa[j+(1<<(i-1))][i-1]);
				fb[j][i]=max(fb[j][i-1],fb[j+(1<<(i-1))][i-1]);
			}
		}
	}
	int aska(int l,int r)
	{
		int t=__lg(r-l+1);
		return max(fa[l][t],fa[r-(1<<t)+1][t]);
	}
	int askb(int l,int r)
	{
		int t=__lg(r-l+1);
		return max(fb[l][t],fb[r-(1<<t)+1][t]);
	}
	const ull B=1e9;
	ull askB(int l,int r)
	{
		if (qb[l*B+r]) return qb[l*B+r];
		if (l>r) return 0;
		int u=askb(l,r);
		u=pb[u];
		ull res=1ll*(u-l+1)*(r-u+1);
		return qb[l*B+r]=askB(l,u-1)+askB(u+1,r)+res*b[u];
	}
	ull ask(int l,int r)
	{
		if (qa[l*B+r]) return qa[l*B+r];
		if (l>r) return 0;
		int u=aska(l,r);
		u=pa[u];
		//cout << l << ' ' << r << " " << u << endl;
		return qa[l*B+r]=ask(l,u-1)+ask(u+1,r)+(askB(l,r)-askB(l,u-1)-askB(u+1,r))*a[u];
	}
	void work()
	{
		n=read();
		for (int i=1;i<=n;i++) a[i]=read();
		for (int i=1;i<=n;i++) b[i]=read();
		for (int i=1;i<=n;i++) pa[a[i]]=i,pb[b[i]]=i;
		STwork();
		int q=read();
		for (int i=1;i<=q;i++)
		{
			int l=read(),r=read();
			cout << ask(l,r) << "\n";
		}
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int id=read();
	if (id<=5) sub1::work();
	else sub2::work();
	return 0;
}
