J. HDZ Explosion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The nuclear power plant (HDZ) on planet A has exploded, turning into ruins. The height of the ruins can be represented by a permutation $$$p$$$ of $$$\{1,2,\ldots,n\}$$$, where the height at position $$$i$$$ is $$$p_i$$$.

Scientists have designed a robot named Bronya with a detection range $$$d$$$ to clean up nuclear waste at the highest point (height $$$n$$$) in the ruins. During airdrop, since precise positioning is impossible, Bronya may land at any position in the ruins. After landing, Bronya begins moving: if Bronya is at position $$$i$$$, she will move to the highest position $$$j$$$ such that $$$\max(1,i-d) \le j \le \min(n,i+d)$$$, repeating this process $$$10^{100}$$$ times. As a scientist, you need to determine the minimum $$$d$$$ such that no matter where Bronya lands initially, she will reach the highest point after all movements.

Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of $$$p$$$.

The second line contains $$$n$$$ distinct integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output the minimum $$$d$$$ that guarantees Bronya will reach the highest position.

Example
Input
3
1
1
5
1 2 3 4 5
10
7 3 1 9 10 2 5 6 4 8
Output
0
1
5