← 返回题目列表

AtCoder · arc060_c

E. 德和酒店

中文机器翻译题面 查看原题

分数: 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.