分数: 700 点
问题陈述
N 酒店位于一条直线上。的坐标 i第酒店 (1 \leq i \leq N) is x_i.
德行旅行者有以下两条个人原则:
- 他旅行的距离从未超过 L 一天之内。
- 他从不在露天睡觉。也就是说,一天结束后他必须入住酒店。
你被给予 Q 查询。的 j-th (1 \leq j \leq Q) 查询由两个不同的整数描述 a_j 和 b_j。 对于每个查询,找出 Tak 从 a_j第1号酒店到 b_j第一个酒店遵循他的原则。 保证他可以随时从 a_j第1号酒店到 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 是整数。
部分分数
- 200 通过满足以下条件的测试集将获得积分 N \leq 10^3 和 Q \leq 10^3.
输入
输入由标准输入按以下格式给出:
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) 应包含 Tak 需要从 a_j第1号酒店到 b_j第一家酒店。
示例输入 1
9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5
示例输出 1
4 2 1 2
对于 1-st查询,他可以从 1-st酒店到 8第 1 家酒店 4 天,如下:
- 天 1:从 1-st酒店到 2-nd 酒店。行驶的距离是 2.
- 天 2:从 2-nd酒店到 4第一家酒店。行驶的距离是 10.
- 天 3:从 4第1号酒店到 7第一家酒店。行驶的距离是 6.
- 天 4:从 7第1号酒店到 8第一家酒店。行驶的距离是 10.