配点 : $700$ 点

問題文

$N$ 軒のホテルが一直線上に並んでいます。$i \, (1 \leq i \leq N)$ 番目のホテルは、座標 $x_i$ に位置しています。

旅行者である高橋君には、次の $2$ つの信念があります。

• 高橋君の $1$ 日の移動距離は $L$ を超えない。
• 高橋君は野宿をしない。すなわち、$1$ 日の終わりには必ずいずれかのホテルにいなければならない。

$Q$ 個のクエリが与えられます。$j\,(1 \leq j \leq Q)$ 番目のクエリとして、異なる $2$ つの整数 $a_j,\,b_j$ が与えられます。 各クエリについて、前述の信念をともに守った上で、高橋君が $a_j$ 番目のホテルから $b_j$ 番目のホテルに移動するために必要な最小日数を求めてください。 なお、高橋君が $a_j$ 番目のホテルから $b_j$ 番目のホテルに移動できることは保証されます。

制約

• $2 \leq N \leq 10^5$
• $1 \leq L \leq 10^9$
• $1 \leq Q \leq 10^5$
• $1 \leq x_i < x_2 < ... < x_N \leq 10^9$
• $x_{i+1} - x_i \leq L$
• $1 \leq a_j,b_j \leq N$
• $a_j \neq b_j$
• $N,\,L,\,Q,\,x_i,\,a_j,\,b_j$ はいずれも整数である

部分点

• $N \leq 10^3$ および $Q \leq 10^3$ を満たすデータセットに正解した場合は、$200$ 点が与えられる。

入力

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

$N$

$x_1$ $x_2$ $...$ $x_N$

$L$

$Q$

$a_1$ $b_1$

$a_2$ $b_2$

:

$a_Q$ $b_Q$

出力

出力は $Q$ 行からなる。 $j \, (1 \leq j \leq Q)$ 行目には、高橋君が $a_j$ 番目のホテルから $b_j$ 番目のホテルに移動するために必要な最小日数を表す整数を出力せよ。

9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

4
2
1
2

$1$ つ目のクエリでは、次のように行動することで、$1$ 番目のホテルから $8$ 番目のホテルへ $4$ 日間で移動することができます。

• $1$ 日目には、$1$ 番目のホテルから $2$ 番目のホテルへ移動する。この日の移動距離は $2$ である。
• $2$ 日目には、$2$ 番目のホテルから $4$ 番目のホテルへ移動する。この日の移動距離は $10$ である。
• $3$ 日目には、$4$ 番目のホテルから $7$ 番目のホテルへ移動する。この日の移動距離は $6$ である。
• $4$ 日目には、$7$ 番目のホテルから $8$ 番目のホテルへ移動する。この日の移動距離は $10$ である。