페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8060
서브태스크

선물 교환 1초 1024MB

문제

JOI 아카데미에는 1번부터 N번까지의 번호가 매겨진 N명의 학생이 있습니다. 곧 JOI 아카데미에서 선물 교환 파티가 열릴 예정입니다. 각 학생은 파티에 가져올 선물을 준비했습니다. 학생 i(1 ≤ i ≤ N)가 가져올 선물의 가치는 Ai입니다. 학생들은 자신의 선물보다 너무 가치가 낮은 선물을 받는 것을 원치 않습니다. 구체적으로, 학생 i는 가치가 Bi보다 작은 선물을 받으면 불만족스러워할 것입니다. 여기서 Bi < Ai는 항상 성립합니다.

그러나 N명의 학생 중 일부는 파티에 실제로 참가하지 않을 수도 있습니다. JOI 아카데미의 회장인 K는 Q개의 가능한 그룹을 고려하고 있으며, 각 그룹은 선물 교환 파티에 참가할 그룹으로 간주됩니다. j번째 그룹(1 ≤ j ≤ Q)은 Rj에서 Lj까지의 학생들로 구성됩니다.

2명 이상의 학생들로 구성된 어떤 그룹에서, 그 그룹 내에서 아무도 자신의 선물을 받거나 불만족하지 않으면서 선물을 교환할 수 있다면, 그 그룹은 "선물 교환 가능(gift exchangeable)"하다고 합니다. 좀 더 구체적으로, m명(m ≥ 2)의 학생들 p1, p2, ..., pm으로 구성된 그룹이 다음 조건을 만족할 경우에만 선물 교환 가능하다고 할 수 있습니다. 여기서 q1, q2, ..., qm은 p1, p2, ..., pm의 순열을 나타내며, qk(1 ≤ k ≤ m)는 학생 pk에게 선물을 주는 학생의 번호를 의미합니다.

  • 모든 k(1 ≤ k ≤ m)에 대해, pk ≠ qk.

  • 모든 k(1 ≤ k ≤ m)에 대해, Aqk ≥ Bpk.

K 회장은 선물 교환 파티가 성공적으로 이루어지길 바라고 있으며, 각 Q개의 그룹이 선물 교환이 가능한지 여부를 확인하고자 합니다.


입력

다음 데이터를 표준 입력에서 읽어들입니다.

N

A1 A2 · · · AN

B1 B2 · · · BN

Q

L1 R1

L2 R2

.

.

.

LQ RQ

[제약 조건]

2 ≤ N ≤ 500,000.

1 ≤ Bi < Ai ≤ 2N (1 ≤ i ≤ N).

A1, B1, A2, B2, ..., AN, BN은 모두 서로 다릅니다.

1 ≤ Q ≤ 200,000.

1 ≤ Lj < Rj ≤ N (1 ≤ j ≤ Q).

주어진 값은 모두 정수입니다.


출력

표준 출력으로 Q개의 줄을 출력합니다. j번째 줄(1 ≤ j ≤ Q)에는 j번째 그룹이 선물 교환 가능하면 "Yes"를, 그렇지 않으면 "No"를 출력하세요.


부분문제

번호 점수 조건
#14점

N ≤ 10, Q ≤ 10

#25점

N ≤ 18, Q ≤ 10

#310점

N ≤ 100,000, A1 ≥ 2N − 2, B1 = 1, Q = 1, L1 = 1, R1 = N

#431점

N ≤ 100,000, Q ≤ 10

#58점

N ≤ 100,000, Ai < Ai+1, Bi < Bi+1 (1 ≤ i ≤ N − 1)

#612점

N ≤ 100,000, Ai < Ai+1 (1 ≤ i ≤ N − 1)

#718점

N ≤ 100,000

#812점

추가 제약 조건 없음


예제1

입력
4
3857
2614
3
34
13
14
출력
Yes
No
Yes

첫 번째 그룹은 학생 3번과 4번으로 구성됩니다. 학생 3번이 학생 4번의 선물을 받고, 학생 4번이 학생 3번의 선물을 받는다면, 두 학생 모두 만족할 수 있으므로 이 그룹은 선물 교환 가능합니다.

두 번째 그룹은 학생 1번, 2번, 3번으로 구성됩니다. 학생 2번은 학생 1번 또는 3번의 선물을 받을 경우 불만족할 것이므로 이 그룹은 선물 교환 불가능합니다.

세 번째 그룹은 학생 1번, 2번, 3번, 4번으로 구성됩니다. 예를 들어, 학생 1번이 학생 2번의 선물을 받고, 학생 2번이 학생 4번의 선물을 받고, 학생 3번이 학생 1번의 선물을 받고, 학생 4번이 학생 3번의 선물을 받는 경우, 모든 학생이 만족할 수 있으므로 이 그룹은 선물 교환 가능합니다.


예제2

입력
3
563
142
1
13
출력
Yes

예제3

입력
5
346910
12578
3
15
12
24
출력
No
Yes
No

예제4

입력
10
25810121416171920
14761113931815
8
29
16
28
24
12
16
710
58
출력
No
No
Yes
No
No
No
Yes
Yes

출처

JOI 2024

역링크