You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述 2s 512MB

注意：本题保证数据随机生成，生成策略在数据范围处。

小明看完田忌赛马的故事以后，觉得田忌赛马很有趣，于是臆想了田忌赛马2。

齐王和田忌各有$n$匹马，田忌第$i$匹马的能力是$a_i$，齐王第$i$匹马的能力是$b_i$。在初始时候，两人各自的马已经按照能力从小到大排好序了，也就是$a_i\leq a_{i+1}$，$b_i\leq b_{i+1}$。由于齐王是君王，所以对于两人的第$i$匹马来说，总是满足$a_i\leq b_i$。

齐王经过第一次田忌赛马以后，很生气，要求在赛马的时候，两个人每次都派出自己最差的马去比赛，直到两人没马为止。

那这田忌不是稳输吗？不，田忌不想坐以待毙，他从遥远的西域国度采购了一种名为星粉剂的神秘药物，每次给一匹马服用，可以使得一匹马的能力$+1$。

齐王自然发现了田忌的神秘药物，因此齐王也提出了一个要求：田忌可以给自己的马服用星粉剂，但是服用之后，需要对自己参赛的马重新按能力排序，然后再进行比赛。

田忌知道自己的星粉剂是无限的，但田忌不敢赢掉齐王，只想让所有比赛都以平局收场。

请帮助田忌算一算，他喂自己的马吃星粉剂有多少种不同的方案吧。由于田忌天生喜欢plan b，所以田忌会多次询问你区间$[l,r]$的答案。

例如：齐王的三匹马能力分别是[3,3,4]，田忌的三匹马能力分别是[1,1,3]，田忌可以把自己的马喂成[3,3,4],[3,4,3],[4,3,3]，来使得每一局都是平局。

顺便给一个形式化题面：

你有两个长度为$n$的正整数单调不递降序列$a,b$。保证$a_i\leq b_i$。你可以生成一个数组$c$满足$c_i\geq a_i$，且$c$数组排序后与$b$相同，问$c$数组的方案数。

多次询问，每次问$a_{[l_i,r_i]}$与$b_{[l_i,r_i]}$对应数组的答案。

输入格式

第一行输入$n$。

接下来一行输入$a_i$。

接下来一行输入$b_i$。

接下来输入$Q$。

接下来$Q$行，每行输入$l_i,r_i$。

输出格式

输出$Q$行，每行输出答案$\mod 998244353$。

10
1 1 2 2 3 3 3 3 4 4
2 2 2 3 3 3 3 4 4 5
5
1 10
2 8
2 5
3 8
3 9

60
15
3
10
10

大样例

数据范围

注意：本题保证数据随机生成。

生成策略是：先手动指定$a$的最大值，随机生成$a$数组，然后$b_i=a_i+random(0,k),k\leq 10$，之后对$b$数组排序。

对于15%的数据：$n\leq 10,Q\leq 10$。

对于30%的数据：$n,Q\leq 1000$。

对于45%的数据：$n\leq 10^5,a_i,b_i\leq 1000$。

对于另15%的数据：$l_i=1$。

对于另15%的数据：$r_i=n$。

对于100%的数据：$n,Q\leq 2\times 10^5,1\leq a_i,b_i\leq n,1\leq l_i<r_i\leq n,a_i\leq b_i$。