P15180 [SWERC 2021] Antennas

在一条直线上有 $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$ 所需的秒数。可以证明在题目约束下，总是可以发送这样的消息。

在第一个测试用例中，我们必须将消息从天线 $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)$。 翻译由 DeepSeek 完成