← 返回题目列表

Codeforces · 1662/F

F. 天线

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

一条线上有 $$$n$$$ 个等距天线,编号从 $$$1$$$ 到 $$$n$$$。每个天线都有一个额定功率,第 $$$i$$$ 个天线的功率为 $$$p_i$$$。

第 $$$i$$$ 和第 $$$j$$$ 天线可以直接通信当且仅当它们的距离最多为其功率的最小值,即 $$$|i-j| \leq \min(p_i, p_j)$$$。在两个这样的天线之间直接发送消息需要 $$$1$$$ 秒。

从天线 $$$a$$$ 向天线 $$$b$$$ 发送消息(可能使用其他天线作为中继)所需的最短时间是多少?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100\,000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$a$$$、$$$b$$$ ($$$1 \leq a, b \leq n \leq 200\,000$$$) — 天线数量以及源天线和目标天线。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — 天线的功率。

所有测试用例的 $$$n$$$ 值的总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,打印将消息从 $$$a$$$ 传输到 $$$b$$$ 所需的秒数。可以证明,在问题约束下,总是可以发送这样的消息。

示例

输入 #1

3
10 2 9
4 1 1 1 5 1 1 1 1 5
1 1 1
1
3 1 3
3 3 1

输出 #1

4
0
2

注意

在第一个测试用例中,我们必须从天线 $$$2$$$ 向天线 $$$9$$$ 发送一条消息。需要 $$$4$$$ 秒(这是可能的最短时间)的通信序列如下:

- 在$$$1$$$第二次,我们将消息从天线$$$2$$$发送到天线$$$1$$$。这是可能的,因为 $$$|2-1|\le \min(1, 4) = \min(p_2, p_1)$$$。
- 在$$$1$$$第二次,我们将消息从天线$$$1$$$发送到天线$$$5$$$。这是可能的,因为 $$$|1-5|\le \min(4, 5) = \min(p_1, p_5)$$$。
- 在 $$$1$$$ 秒内,我们将消息从天线 $$$5$$$ 发送到天线 $$$10$$$。这是可能的,因为 $$$|5-10|\le \min(5, 5) = \min(p_5, p_{10})$$$。
- 在$$$1$$$第二次,我们将消息从天线$$$10$$$发送到天线$$$9$$$。这是可能的,因为 $$$|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$$$。