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?

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.

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