题目描述

题目译自 JOI 2024 Final T4 「プレゼント交換 / Gift Exchange」

JOI 学园有 $N$ 名学生，每个学生都有一个从 $1$ 到 $N$ 的编号。

JOI 学园计划近期举办一个礼物交换会。每个学生都要准备一份礼物带到会场，学生 $i$（$1 \leq i \leq N$）带来的礼物的价值是 $A_i$。学生们都不喜欢收到比自己带来的礼物价值低很多的礼物，具体来说，学生 $i$ 如果收到价值低于 $B_i$ 的礼物，就会感到不满。保证 $B_i < A_i$。

不过，并不是所有 $N$ 名学生都会真的参加礼物交换会。JOI 学园的校长 $K$ 正在考虑 $Q$ 种可能参加礼物交换会的学生组合，第 $j$（$1 \leq j \leq Q$）种组合由 $R_j - L_j + 1$ 名学生 $L_j, L_j+1, \ldots, R_j$ 组成。

对于一个由 $2$ 人以上的学生组成的组合，如果他们可以在组内互换礼物，而不会有人收到自己带来的礼物或者不满意的礼物，那么这个组合就是可行的。准确地说，由 $m$ 名（$m \geq 2$）学生 $p_1, p_2, \ldots, p_m$ 组成的组合是可行的，当且仅当存在一个由 $p_1, p_2, \ldots, p_m$ 重新排列得到的数列 $q_1, q_2, \ldots, q_m$，这里 $q_k$（$1 \leq k \leq m$）表示给学生 $p_k$ 送礼物的学生的编号，满足以下的条件：

1. 对于所有的 $k$（$1 \leq k \leq m$），$p_k \neq q_k$。
2. 对于所有的 $k$（$1 \leq k \leq m$），$A_{q_k} \geq B_{p_k}$。

校长 $K$ 想要让礼物交换会成功的，所以他想要知道这 $Q$ 个组合中，哪些是可行的。

给定学生的信息和组合的信息，对于每个组合，判断它是否是可行的，并编写一个程序来输出结果。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格分隔的整数 $A_1, A_2, \ldots, A_N$。

第三行包含 $N$ 个用空格分隔的整数 $B_1, B_2, \ldots, B_N$。

第四行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含两个整数 $L_i, R_i$。

输出格式

输出 $Q$ 行。第 $j$（$1 \leq j \leq Q$）行如果第 $j$ 个组合是可行的输出 Yes，否则输出 No。

样例 1

输入

$4$ $3$ $8$ $5$ $7$ $2$ $6$ $1$ $4$ $3$ $3$ $4$ $1$ $3$ $1$ $4$

输出

Yes No Yes

说明

第一个组合是由 $2$ 名学生 $3,4$ 组成的。如果学生 $3$ 收到学生 $4$ 的礼物，学生 $4$ 收到学生 $3$ 的礼物，那么由于 $A_3 \geq B_4$ 且 $A_4 \geq B_3$，所以两个学生都不会不满。因此，这个组合是可行的，所以在第一行输出 Yes。

第二个组合是由 $3$ 名学生 $1,2,3$ 组成的。由于 $A_1 < B_2$ 且 $A_3 < B_2$，所以学生 $2$ 不管收到学生 $1$ 还是学生 $3$ 的礼物，都会感到不满。因此，这个组合不是可行的，所以在第二行输出 No。

第三个组合是由 $4$ 名学生 $1,2,3,4$ 组成的。例如，如果学生 $1$ 收到学生 $2$ 的礼物，学生 $2$ 收到学生 $4$ 的礼物，学生 $3$ 收到学生 $1$ 的礼物，学生 $4$ 收到学生 $3$ 的礼物，那么没有人会不满。因此，这个组合是可行的，所以在第三行输出 Yes。这个样例满足子任务 $1,2,4,7,8$ 的限制。

样例 2

输入

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

输出

Yes

说明

这个样例满足子任务 $1,2,3,4,7,8$ 的限制。

样例 3

输入

$5$ $3$ $4$ $6$ $9$ $10$ $1$ $2$ $5$ $7$ $8$ $3$ $1$ $5$ $1$ $2$ $2$ $4$

输出

No Yes No

说明

这个样例满足子任务 $1,2,4,5,6,7,8$ 的限制。

样例 4

输入

$10$ $2$ $5$ $8$ $10$ $12$ $14$ $16$ $17$ $19$ $20$ $1$ $4$ $7$ $6$ $11$ $13$ $9$ $3$ $18$ $15$ $8$ $2$ $9$ $1$ $6$ $2$ $8$ $2$ $4$ $1$ $2$ $1$ $6$ $7$ $10$ $5$ $8$

输出

No No Yes No No No Yes Yes

说明

这个样例满足子任务 $1,2,4,6,7,8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5\times 10^5$
• $1 \leq B_i < A_i \leq 2N$（$1 \leq i \leq N$）
• $A_1, B_1, A_2, B_2, \ldots, A_N, B_N$ 各不相同
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq L_j < R_j \leq N$（$1 \leq j \leq Q$）

详细子任务附加限制及分值如下表所示：

子任务	附加限制	分值
$1$	$N \leq 10$，$Q \leq 10$	$4$
$2$	$N \leq 18$，$Q \leq 10$	$5$
$3$	$N \leq 10^5$，$A_1 \geq 2N-2$，$B_1=1$，$Q=1$，$L_1=1$，$R_1=N$	$10$
$4$	$N \leq 10^5$，$Q \leq 10$	$31$
$5$	$N \leq 10^5$，$A_i < A_{i+1}$，$B_i < B_{i+1}$（$1 \leq i \leq N-1$）	$8$
$6$	$N \leq 10^5$，$A_i < A_{i+1}$（$1 \leq i \leq N-1$）	$12$
$7$	$N \leq 10^5$	$18$
$8$	无附加限制	$12$