O - Swapping Desks Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N 個の机が横一列に並んでいます。机 i\,(1 \leq i \leq N) は初期状態で左から i 番目にあり、重さは A_i です。PCT 君は以下の操作を任意回行うことができます。

  • 隣り合っている 2 つの机を選ぶ。これらの重さの和が K 以下のとき、これらの場所を入れ替える。

Q 個の独立なクエリが与えられます。i 番目のクエリでは、PCT 君が机 s_i を左から t_i 番目に移動させることができるか判定してください。

制約

  • 1 \leq N,Q \leq 2\times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq s_i,t_i \leq N
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q K
A_1 A_2 \ldots A_N
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q

出力

Q 行出力せよ。i\,(1 \leq i \leq Q) 行目には、机 s_i を左から t_i 番目に移動させることができるならば Yes、そうでないなら No と出力せよ。

入力例 1

3 3 4
1 2 3
1 3
3 1
2 3

出力例 1

Yes
No
No

1 番目のクエリでは、机 1 と机 2 を入れ替えた後、机 1 と机 3 を入れ替えると、机 1 を左から 3 番目に移動させることができるので、Yes を出力します。

入力例 2

4 1 1
100 100 100 100
1 1

出力例 2

Yes

操作を行わなくても構いません。

入力例 3

8 3 10
4 1 1 3 6 4 3 6
5 7
3 3
1 1

出力例 3

Yes
Yes
Yes