CF1662F.Antennas

There are $n$ equidistant antennas on a line, numbered from $1$ to $n$. Each antenna has a power rating, the power of the $i$-th antenna is $p_i$.

The $i$-th and the $j$-th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., $|i-j| \leq \min(p_i, p_j)$. Sending a message directly between two such antennas takes $1$ second.

What is the minimum amount of time necessary to send a message from antenna $a$ to antenna $b$, possibly using other antennas as relays?

一条直线上有 $n$ 个等距排列的天线，编号从 $1$ 到 $n$。每个天线有一个功率值，第 $i$ 个天线的功率为 $p_i$。

当且仅当两个天线之间的距离不超过它们功率的最小值时，第 $i$ 个天线与第 $j$ 个天线才能直接通信，即满足 $|i-j| \leq \min(p_i, p_j)$。在满足该条件的任意两个天线之间直接发送一条消息耗时 $1$ 秒。

请问：从天线 $a$ 向天线 $b$ 发送一条消息（允许经由其他天线中继）所需的最短时间是多少？

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 100\,000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains three integers $n$, $a$, $b$ ($1 \leq a, b \leq n \leq 200\,000$) — the number of antennas, and the origin and target antenna.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq n$) — the powers of the antennas.

The sum of the values of $n$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print the number of seconds needed to trasmit a message from $a$ to $b$. It can be shown that under the problem constraints, it is always possible to send such a message.

对于每个测试用例，输出从节点 $a$ 向节点 $b$ 传输一条消息所需的秒数。在本题的约束条件下，可以证明总能成功发送该消息。

In the first test case, we must send a message from antenna $2$ to antenna $9$. A sequence of communications requiring $4$ seconds, which is the minimum possible amount of time, is the following:

• In $1$ second we send the message from antenna $2$ to antenna $1$. This is possible since $|2-1|\le \min(1, 4) = \min(p_2, p_1)$.
• In $1$ second we send the message from antenna $1$ to antenna $5$. This is possible since $|1-5|\le \min(4, 5) = \min(p_1, p_5)$.
• In $1$ second we send the message from antenna $5$ to antenna $10$. This is possible since $|5-10|\le \min(5, 5) = \min(p_5, p_{10})$.
• In $1$ second we send the message from antenna $10$ to antenna $9$. This is possible since $|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$.

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