A15051 | $Antennas$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

输入 #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

C++ 编辑器

输入

输出