N. Cheap Sort
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. The elements of the array are numbered from $$$1$$$ to $$$n$$$.

To sort the subarray $$$a[l, r]$$$ is to reorder all elements $$$a_l, a_{l+1}, \dots, a_r$$$ so that they are in non-decreasing order, without affecting any other elements of the array $$$a$$$. For example, if $$$a = [3, 5, 2, 1, 7, 4, 6]$$$ and you sort $$$a[2, 5]$$$, you get $$$[3, 1, 2, 5, 7, 4, 6]$$$. Sorting the subarray $$$a[l,r]$$$ costs $$$(r-l+1)$$$ coins. You can also sort an empty subarray; this costs $$$0$$$ coins and does not change the array at all.

You want to sort the subarray $$$a[L, R]$$$. However, this might be too wasteful, as there might be another subarray $$$a[L', R']$$$ such that sorting it yields the same result as sorting $$$a[L, R]$$$ but is cheaper.

So, your task is the following: find the minimum possible cost of one sorting operation that yields the same result as sorting $$$a[L, R]$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines. The first line contains three integers $$$n, L, R$$$ ($$$1 \le L \le R \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum cost of one sorting operation that yields the same result as sorting $$$a[L, R]$$$.

Example
Input
3
7 2 5
3 5 2 1 7 4 6
5 2 5
5 1 2 3 4
5 1 5
5 1 2 3 4
Output
3
0
5
Note

In the first example, you can sort $$$a[2, 4]$$$.

In the second example, you can sort an empty subarray.

In the third example, you have to sort the whole array $$$a$$$ (i. e. $$$a[1, 5]$$$).