G. Going Along the Circle
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

For the purposes of this problem, a permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.

A permutation of the integers from $$$1$$$ to $$$n$$$ is written down at $$$n$$$ positions around a circle. From any position, you can go in one step to a neighboring position in the clockwise direction.

Start at the number $$$1$$$ and go only clockwise: first to the number $$$2$$$, then to the number $$$3$$$, and so on up to the number $$$n$$$. The length of the walk from $$$i$$$ to $$$i + 1$$$ is the number of clockwise steps needed to go from the position of number $$$i$$$ to the position of number $$$i + 1$$$. Find the minimum and the maximum among these $$$n - 1$$$ lengths.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The first line of a test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$): the number of positions on the circle.

The second line of a test case contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$): the integers at the positions in clockwise order. These integers form a permutation of the integers from $$$1$$$ to $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two integers from $$$1$$$ to $$$n - 1$$$ on a separate line: the minimum walk length, then the maximum walk length.

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

In the first test case of the example, $$$n = 6$$$ and the integers $$$1$$$, $$$4$$$, $$$2$$$, $$$6$$$, $$$3$$$, $$$5$$$ are written down clockwise. The lengths of the walks from $$$1$$$ to $$$2$$$, from $$$2$$$ to $$$3$$$, from $$$3$$$ to $$$4$$$, from $$$4$$$ to $$$5$$$, and from $$$5$$$ to $$$6$$$ are $$$2$$$, $$$2$$$, $$$3$$$, $$$4$$$, and $$$4$$$, respectively, so the minimum is $$$2$$$ and the maximum is $$$4$$$.