题目描述

$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$ 番目のホテルに移動できることは保証されます。

输入格式

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

$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$ 番目のホテルに移動するために必要な最小日数を表す整数を出力せよ。

题目大意

题意翻译

Translated by aoweiyin

一条笔直的公路上有$N$个旅店，第$i$个旅店的坐标是$x_i$

高桥君旅行时有如下习惯：

• 他一天最多行走长度不大于$L$的路程
• 他一定会选择一家旅店作为自己一天行程的终点

现在他有$Q$组行程计划，对于每一组计划，他会从旅店a旅行到旅店b$(a\neq b)$。你现在需要帮助他，求出每一组计划所需的最小天数

输出格式：

$N$

$x_1\ x_2\ \dots\ x_N$

$L$

$Q$

$a_1\ b_1$

$a_2\ b_2$

$\dots$

$a_Q\ b_Q$

输出格式：

第$i$行输出第$i$组计划的最优解

数据范围：

有200分的数据满足$N\leq 10^3$,$Q\leq 10^3$

对于所有数据满足$2\leq N\leq 10^5$,$1\leq L\leq 10^9$,$1\leq Q\leq 10^5$

$1\leq x_1<x_2<\dots<x_N\leq 10^9$

$x_{i+1}-x_i\leq L$

保证所有数为整数，且一定存在最优解

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

4
2
1
2

提示

制約

• $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$ 点が与えられる。

Sample Explanation 1

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