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.
样例
样例输入 1
3
10 2 9
4 1 1 1 5 1 1 1 1 5
1 1 1
1
3 1 3
3 3 1
样例输出 1
4
0
2
数据范围与提示
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 .
