F. Antennas
data structures; dfs and similar; graphs; graphs; implementation; implementation; shortest paths; shortest paths
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)\).