codeforces#P1662F. Antennas

    ID: 32831 远端评测题 4000ms 256MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>data structuresdfs and similargraphsgraphsimplementationimplementationshortest pathsshortest paths

Antennas

Description

There are nn equidistant antennas on a line, numbered from 11 to nn. Each antenna has a power rating, the power of the ii-th antenna is pip_i.

The ii-th and the jj-th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., ijmin(pi,pj)|i-j| \leq \min(p_i, p_j). Sending a message directly between two such antennas takes 11 second.

What is the minimum amount of time necessary to send a message from antenna aa to antenna bb, possibly using other antennas as relays?

Each test contains multiple test cases. The first line contains an integer tt (1t1000001\le t\le 100\,000) — the number of test cases. The descriptions of the tt test cases follow.

The first line of each test case contains three integers nn, aa, bb (1a,bn2000001 \leq a, b \leq n \leq 200\,000) — the number of antennas, and the origin and target antenna.

The second line contains nn integers p1,p2,,pnp_1, p_2, \dots, p_n (1pin1 \leq p_i \leq n) — the powers of the antennas.

The sum of the values of nn over all test cases does not exceed 200000200\,000.

For each test case, print the number of seconds needed to trasmit a message from aa to bb. 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 tt (1t1000001\le t\le 100\,000) — the number of test cases. The descriptions of the tt test cases follow.

The first line of each test case contains three integers nn, aa, bb (1a,bn2000001 \leq a, b \leq n \leq 200\,000) — the number of antennas, and the origin and target antenna.

The second line contains nn integers p1,p2,,pnp_1, p_2, \dots, p_n (1pin1 \leq p_i \leq n) — the powers of the antennas.

The sum of the values of nn over all test cases does not exceed 200000200\,000.

Output

For each test case, print the number of seconds needed to trasmit a message from aa to bb. It can be shown that under the problem constraints, it is always possible to send such a message.

Samples

输入数据 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

Note

In the first test case, we must send a message from antenna 22 to antenna 99. A sequence of communications requiring 44 seconds, which is the minimum possible amount of time, is the following:

  • In 11 second we send the message from antenna 22 to antenna 11. This is possible since 21min(1,4)=min(p2,p1)|2-1|\le \min(1, 4) = \min(p_2, p_1).
  • In 11 second we send the message from antenna 11 to antenna 55. This is possible since 15min(4,5)=min(p1,p5)|1-5|\le \min(4, 5) = \min(p_1, p_5).
  • In 11 second we send the message from antenna 55 to antenna 1010. This is possible since 510min(5,5)=min(p5,p10)|5-10|\le \min(5, 5) = \min(p_5, p_{10}).
  • In 11 second we send the message from antenna 1010 to antenna 99. This is possible since 109min(5,1)=min(p10,p9)|10-9|\le \min(5, 1) = \min(p_{10}, p_9).