codeforces#P1662F. Antennas
Antennas
Description
There are equidistant antennas on a line, numbered from to . Each antenna has a power rating, the power of the -th antenna is .
The -th and the -th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., . Sending a message directly between two such antennas takes second.
What is the minimum amount of time necessary to send a message from antenna to antenna , possibly using other antennas as relays?
Each test contains multiple test cases. The first line contains an integer () — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains three integers , , () — the number of antennas, and the origin and target antenna.
The second line contains integers () — the powers of the antennas.
The sum of the values of over all test cases does not exceed .
For each test case, print the number of seconds needed to trasmit a message from to . It can be shown that under the problem constraints, it is always possible to send such a message.
Input
Each test contains multiple test cases. The first line contains an integer () — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains three integers , , () — the number of antennas, and the origin and target antenna.
The second line contains integers () — the powers of the antennas.
The sum of the values of over all test cases does not exceed .
Output
For each test case, print the number of seconds needed to trasmit a message from to . It can be shown that under the problem constraints, it is always possible to send such a message.
Samples
Note
In the first test case, we must send a message from antenna to antenna . A sequence of communications requiring seconds, which is the minimum possible amount of time, is the following:
- In second we send the message from antenna to antenna . This is possible since .
- In second we send the message from antenna to antenna . This is possible since .
- In second we send the message from antenna to antenna . This is possible since .
- In second we send the message from antenna to antenna . This is possible since .