Problem Description

There are $N$ students at JOI Academy, and each student has an ID number from $1$ to $N$.

JOI Academy is planning to hold a gift exchange party soon. Each student will bring one gift to the venue, and the value of the gift brought by student $i\ (1 \leq i \leq N)$ is $A_{i}$. Students do not like to receive a gift whose value is much lower than the one they brought. More specifically, student $i$ will be dissatisfied if they receive a gift with value less than $B_{i}$. It is guaranteed that $B_{i}<A_{i}$.

However, not all $N$ students will actually participate in the gift exchange party. The principal K of JOI Academy is considering $Q$ possible groups of students who may participate. The $j\ (1 \leq j \leq Q)$-th group consists of $R_{j}-L_{j}+1$ students $L_{j}, L_{j}+1, \ldots, R_{j}$.

For a group consisting of at least $2$ students, if they can exchange gifts within the group such that nobody receives their own gift and nobody receives an unsatisfying gift, then the group is feasible. More precisely, a group consisting of $m$ $(m \geq 2)$ students $p_{1}, p_{2}, \ldots, p_{m}$ is feasible if and only if there exists a sequence $q_{1}, q_{2}, \ldots, q_{m}$ obtained by permuting $p_{1}, p_{2}, \ldots, p_{m}$, where $q_{k}\ (1 \leq k \leq m)$ denotes the ID of the student who gives a gift to student $p_{k}$, such that the following conditions are satisfied:

• For all $k\ (1 \leq k \leq m)$, $p_{k} \neq q_{k}$.
• For all $k\ (1 \leq k \leq m)$, $A_{q_{k}} \geq B_{p_{k}}$.

Principal K wants the gift exchange party to be successful, so he wants to know which of these $Q$ groups are feasible.

Given the information about the students and the groups, determine for each group whether it is feasible, and write a program to output the results.

Input Format

The first line contains an integer $N$.

The second line contains $N$ space-separated integers $A_1,A_2,\ldots ,A_N$.

The third line contains $N$ space-separated integers $B_1,B_2,\ldots ,B_N$.

The fourth line contains an integer $Q$.

Each of the next $Q$ lines contains two integers $L_i,R_i$.

Output Format

Output $Q$ lines. On the $j\ (1 \leq j \leq Q)$-th line, output Yes if the $j$-th group is feasible; otherwise output No.

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

Yes
No
Yes

Hint

Explanation of the samples

The first group consists of 2 students 3 and 4. If student 3 receives student 4's gift and student 4 receives student 3's gift, then since $A_{3} \geq B_{4}$ and $A_{4} \geq B_{3}$, neither student will be dissatisfied. Therefore, this group is feasible, so output Yes on the first line.

The second group consists of 3 students 1, 2, and 3. Since $A_{1}<B_{2}$ and $A_{3}<B_{2}$, student 2 will be dissatisfied no matter whether they receive the gift from student 1 or student 3. Therefore, this group is not feasible, so output No on the second line.

The third group consists of 4 students 1, 2, 3, and 4. For example, if student 1 receives student 2's gift, student 2 receives student 4's gift, student 3 receives student 1's gift, and student 4 receives student 3's gift, then nobody will be dissatisfied. Therefore, this group is feasible, so output Yes on the third line.

This sample satisfies the constraints of subtasks 1, 2, 4, 7, and 8.

Constraints

For all input data, the following hold:

• $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}$ are all distinct.
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq L_{j}<R_{j} \leq N\ (1 \leq j \leq Q)$

The additional constraints and scores for subtasks are shown in the table below.

Translated by ChatGPT 5