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.
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$$$.
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.
661 4 2 6 3 531 2 332 3 151 2 5 4 344 3 2 141 3 2 4
2 41 11 11 43 32 3
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$$$.
| Name |
|---|


