#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

constexpr int mod = 998'244'353;
int add(int a, int b) {
    return a + b - mod * (a + b >= mod);
}
void add_to(int& a, int b) {
    a = add(a, b);
}
int mul(int a, int b) {
    return a * 1ULL * b % mod;
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n);
    for (auto& i : a) {
        std::cin >> i;
    }
    for (auto& i : b) {
        std::cin >> i;
    }
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    b.insert(b.end(), n + 1, -1);

    int64_t all = 0;
    auto count = [&](int cnt) -> int {
        std::vector<int> dp(cnt + 1);
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            int s = a[i];
            int lb = std::max(0, n - cnt - 3);
            for (int j = std::min(i + 1, cnt); j >= lb; j--) {
                dp[j] = add(dp[j] * (s < b[cnt + (i - j)]),
                            (j != 0) * (dp[j - 1] * (b[j - 1] < s)));
                all++;
            }
        }
        return dp[cnt];
    };

    std::vector<int> ans(n + 1, -1);
    for (int cnt = 0; cnt <= n; cnt++) {
        ans[cnt] = count(cnt);
    }

    std::cerr << all / pow(n, 3) << "\n";

    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        int sum = 0;
        for (int i = l; i <= r; i++) {
            if (ans[i] == -1) {
                ans[i] = count(i);
            }
            add_to(sum, ans[i]);
        }
        std::cout << sum << " \n"[i == q - 1];
    }

    return 0;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~