题目描述

有 $n$ 个英雄和 $n$ 个怪物。英雄和怪物分别编号为 $1$ 到 $n$ 的整数。第 $i$ 个英雄的战斗力为 $a_i$，第 $i$ 个怪物的战斗力为 $b_i$。保证所有 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ 的值都是两两不同的。

将进行总共 $n$ 场战斗。每场战斗中恰好有一个英雄和一个怪物参与，且每个英雄和每个怪物都恰好参与一场战斗。假设某场战斗由编号为 $i$ 的英雄和编号为 $j$ 的怪物进行。如果 $a_i > b_j$，则编号为 $i$ 的英雄会感到高兴；否则，他会感到悲伤。

定义 $ans_k$ 为大小为 $k$ 的不同英雄集合 $S$ 的数量，满足存在一种战斗分配方式使得集合 $S$ 中的所有英雄都高兴，而其他英雄都悲伤。

给定 $q$ 个形如 $l$、$r$ 的查询。对于每个查询，计算 $(\sum\limits_{i=l}^{r} ans_i) \mod 998244353$ 的值。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^3$）—— 将进行的战斗场数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 2 \cdot n$）—— 英雄的战斗力。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 2 \cdot n$）—— 怪物的战斗力。

保证所有 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ 的值都是两两不同的。

第四行包含一个整数 $q$（$1 \leq q \leq n+1$）—— 查询的数量。

接下来的 $q$ 行每行包含两个整数 $l$ 和 $r$（$0 \leq l \leq r \leq n$）—— 对应查询的参数。

保证所有 $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$ 的值都是两两不同的。

输出格式

对于每个查询，输出一个整数 —— 所求的值 $(\sum\limits_{i=l}^{r} ans_i) \mod 998244353$。

3
3 4 6
1 2 5
3
1 2
2 3
3 3

2
3
1

提示

下图展示了第一个样例中的英雄和怪物。英雄位于上方，怪物位于下方。方块中的数字表示对应英雄或怪物的战斗力。

在样例中，存在三个可能的高兴英雄集合：$\{1,2,3\}$、$\{2,3\}$ 和 $\{1,3\}$。以下是三种可能的战斗分配方式，使得对应的英雄集合高兴。注意，可能存在多种战斗分配方式使得同一个英雄集合高兴。

评分标准

• （$3$ 分）：对于所有 $1 \leq i,j \leq n$，满足 $a_i < b_j$；
• （$9$ 分）：$q = 1$，$l = 1$，$r = 1$；
• （$6$ 分）：对于所有 $1 \leq i \leq n$，满足 $a_i = 2 \cdot i - 1$，$b_i = 2 \cdot i$；
• （$16$ 分）：$n \leq 500$，$q = 1$，$l = 0$，$r = n$；
• （$14$ 分）：$q = 1$，$l = 0$，$r = n$；
• （$15$ 分）：$q = 1$，$l = r$；
• （$17$ 分）：$n \leq 500$；
• （$20$ 分）：无额外限制。

翻译由 DeepSeek V3 完成