Antennas

# Antennas ## 题目描述 $ n $ 架间距相等的天线站成一排，从左到右以 $ 1 $ 到 $ n $ 作为编号。每架天线有一个额定发射功率，编号为 $ i $ 的天线发射功率为 $ p_i $。 当且仅当满足 $ |i-j| \leq \min(p_i, p_j) $ ，编号为 $ i $ 和 $ j $ 的天线可以直接传递信息。两架天线传递一条信息需要 $ 1 $ 秒种。 现在需要从 $ a $ 天线向 $ b $ 天线发射一条信息，可以用其他天线作为中继，请问最短需要多长时间发送出这条信息？ ## 输入格式 本题每个测试点包含多组数据。每个测试点第一行包含一个整数 $ t $ ( $ 1\le t\le 100\,000 $ ) 表示数据的组数。紧接着给出每组数据的内容。 每组数据的第一行包含三个整数 $ 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$ 之和不会超过 $200000$。 ## 输出格式 对于每组数据，输出从 $a$ 到 $b$ 发送一条信息需要的最短时间。数据保证一定有解。 ## 样例 #1 提示 在第一组数据中，我们要从 $ 2 $ 号天线到 $ 9 $ 号天线发射一条信息，可以证明最短耗时是 $ 4 $ 分钟： - 由 $ 2 $ 号发射到 $ 1 $ 号 花费 $ 1 $ 秒。 $ |2-1|\le \min(1, 4) = \min(p_2, p_1) $. - 由 $ 1 $ 号发射到 $ 5 $ 号 花费 $ 1 $ 秒。 $ |1-5|\le \min(4, 5) = \min(p_1, p_5) $. - 由 $ 5 $ 号发射到 $ 10 $ 号 花费 $ 1 $ 秒。 $ |5-10|\le \min(5, 5) = \min(p_5, p_{10}) $. - 由 $ 10 $ 号发射到 $ 9 $ 号 花费 $ 1 $ 秒。$ |10-9|\le \min(5, 1) = \min(p_{10}, p_9) $ .

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?

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 $ .

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.

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

4
0
2

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) $ .