AT_joi2024ho_d プレゼント交換 (Gift Exchange)

JOI 学園には $ N $ 人の生徒がおり，それぞれ $ 1 $ から $ N $ までの番号が付けられている． JOI 学園では，近日プレゼント交換会が開催される予定である． 各生徒はそこに持参するためのプレゼントを $ 1 $ つずつ用意しており，生徒 $ i $ ( $ 1\leqq i \leqq N $ ) が持参する予定のプレゼントの価値は $ A_i $ である． 生徒たちは自分が持参したプレゼントに比べて価値が低すぎるプレゼントを貰うことを嫌がっており，具体的には，生徒 $ i $ は価値 $ B_i $ 未満のプレゼントを受け取ると不満を抱く． ここで， $ B_i < A_i $ が成り立っている． ただし， $ N $ 人の生徒全員がプレゼント交換会に実際に参加するとは限らない． JOI 学園のトップである K 理事長は，プレゼント交換会に参加する生徒のグループとして $ Q $ 個の可能性を検討しており， $ j $ 個目 ( $ 1\leqq j\leqq Q $ ) のグループは $ R_j-L_j+1 $ 人の生徒 $ L_j,L_j+1,\dots,R_j $ からなる． ある $ 2 $ 人以上の生徒のグループについて，誰かが自分の持参したプレゼントを受け取ったり不満を抱いたりすることなくグループ内でプレゼントを交換できるとき，そのグループは**プレゼント交換可能**であるという． 厳密には， $ m $ 人 ( $ m \geqq 2 $ ) の生徒 $ p_1,p_2,\dots,p_m $ からなるグループが**プレゼント交換可能**であるとは， $ p_1,p_2,\dots,p_m $ を並び替えてできる数列 $ q_1,q_2,\dots,q_m $ であって，以下の条件を共に満たすものが存在することをいう． なお， $ q_k $ ( $ 1\leqq k\leqq m $ ) は生徒 $ p_k $ にプレゼントを渡す生徒の番号を表している． - すべての $ k $ ( $ 1\leqq k\leqq m $ ) について， $ p_k \neq q_k $ ． - すべての $ k $ ( $ 1\leqq k\leqq m $ ) について， $ A_{q_k} \geqq B_{p_k} $ ． プレゼント交換会を成功させたい K 理事長は， $ Q $ 個のグループそれぞれについてプレゼント交換可能であるかどうかを調べようとしている． 生徒の情報とグループの情報が与えられたとき，それぞれのグループについてプレゼント交換可能であるかどうかを判定するプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

標準出力に $ Q $ 行で出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には， $ j $ 個目のグループがプレゼント交換可能であるならば `Yes` を，そうでないならば `No` を出力せよ． ---

### 小課題 1. ( $ 4 $ 点) $ N \leqq 10 $ ， $ Q \leqq 10 $ ． 2. ( $ 5 $ 点) $ N \leqq 18 $ ， $ Q \leqq 10 $ ． 3. ( $ 10 $ 点) $ N \leqq 100\,000 $ ， $ A_1 \geqq 2N-2 $ ， $ B_1=1 $ ， $ Q=1 $ ， $ L_1=1 $ ， $ R_1=N $ ． 4. ( $ 31 $ 点) $ N \leqq 100\,000 $ ， $ Q \leqq 10 $ ． 5. ( $ 8 $ 点) $ N \leqq 100\,000 $ ， $ A_i < A_{i+1} $ ， $ B_i < B_{i+1} $ ( $ 1\leqq i\leqq N-1 $ )． 6. ( $ 12 $ 点) $ N \leqq 100\,000 $ ， $ A_i < A_{i+1} $ ( $ 1\leqq i\leqq N-1 $ )． 7. ( $ 18 $ 点) $ N \leqq 100\,000 $ ． 8. ( $ 12 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 1 $ 個目のグループは， $ 2 $ 人の生徒 $ 3,4 $ からなる． 生徒 $ 3 $ が生徒 $ 4 $ のプレゼントを，生徒 $ 4 $ が生徒 $ 3 $ のプレゼントを受け取った場合， $ A_3\geqq B_4 $ かつ $ A_4\geqq B_3 $ より，どちらの生徒も不満を抱かない． よって，このグループはプレゼント交換可能であるので， $ 1 $ 行目には `Yes` を出力する． $ 2 $ 個目のグループは， $ 3 $ 人の生徒 $ 1,2,3 $ からなる． $ A_1 < B_2 $ かつ $ A_3 < B_2 $ より，生徒 $ 2 $ は生徒 $ 1,3 $ のいずれのプレゼントを受け取っても不満を抱いてしまう． よって，このグループはプレゼント交換可能でないので， $ 2 $ 行目には `No` を出力する． $ 3 $ 個目のグループは， $ 4 $ 人の生徒 $ 1,2,3,4 $ からなる． たとえば，生徒 $ 1 $ が生徒 $ 2 $ のプレゼントを，生徒 $ 2 $ が生徒 $ 4 $ のプレゼントを，生徒 $ 3 $ が生徒 $ 1 $ のプレゼントを，生徒 $ 4 $ が生徒 $ 3 $ のプレゼントを受け取れば誰も不満を抱かない． よって，このグループはプレゼント交換可能であるので， $ 3 $ 行目には `Yes` を出力する． この入力例は小課題 $ 1,2,4,7,8 $ の制約を満たす． --- ### Sample Explanation 2 この入力例は小課題 $ 1,2,3,4,7,8 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1,2,4,5,6,7,8 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 1,2,4,6,7,8 $ の制約を満たす． ### Constraints - $ 2 \leqq N \leqq 500\,000 $ ． - $ 1 \leqq B_i < A_i \leqq 2N $ ( $ 1\leqq i\leqq N $ )． - $ A_1,B_1,A_2,B_2,\dots,A_N,B_N $ はすべて異なる． - $ 1 \leqq Q \leqq 200\,000 $ ． - $ 1 \leqq L_j < R_j \leqq N $ ( $ 1\leqq j\leqq Q $ )． - 入力される値はすべて整数である．