#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

mt19937 gen(time(0));

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 5005, MOD = 998244353;

// CALC
inline void inc (int &x, int y) { x += y - MOD; x += (x >> 31) & MOD; }
inline int qpow (int a, int b) { int res = 1; for(; b; b >>= 1, a = 1ll * a * a % MOD) if(b & 1) res = 1ll * res * a % MOD; return res; }
inline int qinv (int a) { return qpow(a, MOD - 2); }

struct mint {
	int x; 
	mint (int ix = 0) { x = ix % MOD; if(x < 0) x += MOD; }
	mint operator += (mint a) { inc (x, a.x); return a; }
	mint operator -= (mint a) { inc (x, MOD - a.x); return a; }
	mint operator *= (mint a) { x = 1ll * x * a.x % MOD; return a; }
	mint friend operator + (mint a, mint b) { a += b; return a; }
	mint friend operator - (mint a, mint b) { a -= b; return a; }
	mint friend operator * (mint a, mint b) { a *= b; return a; }
} f[N << 1][N], g[N << 1][N], ans[N];  

int n, m, a[N], b[N];
pii A[N << 1];

signed main() {
	n = read (); A[0] = mkp (1, 0);
	rep (i, 1, n) A[a[i] = read ()] = mkp (0, i);
	rep (i, 1, n) A[b[i] = read ()] = mkp (1, i);
	
	{
		int ca = 0, cb = 0;
		f[0][0] = 1;
		rep (i, 1, 2 * n) {
			auto [u, v] = A[i];
			if (u == 0) {
				++ ca;
				rep (j, 0, min (ca, cb)) f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
			}
			else {
				++ cb;
				rep (j, 0, min (ca, cb)) f[i][j] = f[i - 1][j];
			}
		}
	}
	
	{
		int ca = 0, cb = 0;
		g[2 * n + 1][0] = 1;
		lep (i, 2 * n, 1) {
			auto [u, v] = A[i];
			if (u == 0) {
				++ ca; 
				rep (j, 0, min (ca, cb)) g[i][j] = g[i + 1][j] + g[i + 1][j - 1];
			}
			else {
				++ cb;
				rep (j, 0, min (ca, cb)) g[i][j] = g[i + 1][j];
			}
		}
	}
	
	int pr = 0, sf = n;
	rep (i, 0, 2 * n) {
		auto [u, v] = A[i];
		if (!u) { ++ pr, -- sf; continue; }
		ans[v + 1] += ans[v];
		rep (j, 0, pr) ans[v + 1] += f[i][j] * g[i][sf - (i - pr - j)];
	}
	
	m = read ();
	for (int i = 1, l, r; i <= m; i ++)
		l = read (), r = read (), printf ("%d\n", (ans[r + 1] - ans[l]).x);
	
	return 0;
}