一条线上有 $$$n$$$ 个等距天线,编号从 $$$1$$$ 到 $$$n$$$。每个天线都有一个额定功率,第 $$$i$$$ 个天线的功率为 $$$p_i$$$。
第 $$$i$$$ 和第 $$$j$$$ 天线可以直接通信当且仅当它们的距离最多为其功率的最小值,即 $$$|i-j| \leq \min(p_i, p_j)$$$。在两个这样的天线之间直接发送消息需要 $$$1$$$ 秒。
从天线 $$$a$$$ 向天线 $$$b$$$ 发送消息(可能使用其他天线作为中继)所需的最短时间是多少?
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100\,000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$a$$$、$$$b$$$ ($$$1 \leq a, b \leq n \leq 200\,000$$$) — 天线数量以及源天线和目标天线。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — 天线的功率。
所有测试用例的 $$$n$$$ 值的总和不超过 $$$200\,000$$$。
输出
对于每个测试用例,打印将消息从 $$$a$$$ 传输到 $$$b$$$ 所需的秒数。可以证明,在问题约束下,总是可以发送这样的消息。
示例
输入 #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
注意
在第一个测试用例中,我们必须从天线 $$$2$$$ 向天线 $$$9$$$ 发送一条消息。需要 $$$4$$$ 秒(这是可能的最短时间)的通信序列如下:
- 在$$$1$$$第二次,我们将消息从天线$$$2$$$发送到天线$$$1$$$。这是可能的,因为 $$$|2-1|\le \min(1, 4) = \min(p_2, p_1)$$$。
- 在$$$1$$$第二次,我们将消息从天线$$$1$$$发送到天线$$$5$$$。这是可能的,因为 $$$|1-5|\le \min(4, 5) = \min(p_1, p_5)$$$。
- 在 $$$1$$$ 秒内,我们将消息从天线 $$$5$$$ 发送到天线 $$$10$$$。这是可能的,因为 $$$|5-10|\le \min(5, 5) = \min(p_5, p_{10})$$$。
- 在$$$1$$$第二次,我们将消息从天线$$$10$$$发送到天线$$$9$$$。这是可能的,因为 $$$|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$$$。