C. Reverse and Double
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.

In one operation, you choose two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). Then the segment $$$a_l, a_{l+1}, \ldots, a_r$$$ is reversed, and every value in this segment is doubled.

In other words, after applying the operation, the chosen segment becomes $$$2\cdot a_r, 2\cdot a_{r-1}, \ldots, 2\cdot a_l$$$ and the full array is $$$$$$[a_1, a_2, \ldots, a_{l-1}, 2\cdot a_r, 2\cdot a_{r-1}, \ldots, 2\cdot a_l, a_{r+1}, \ldots, a_n].$$$$$$

The gap value of an array is the maximum value of $$$|a_i-a_{i+1}|$$$ over all $$$1 \le i \lt n$$$.

Find the minimum possible gap value of $$$a$$$ after applying at most one operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 3\cdot 10^5$$$) — the length of $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

It is guaranteed that 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 possible gap value after applying at most one operation.

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

In the first test case, it is optimal to choose $$$l = 4$$$ and $$$r = 5$$$. The resulting array is $$$$$$[9, 9, 8, \mathbf{8}, \mathbf{4}, 4, 3, 5, 3]$$$$$$ and the resulting gap value is $$$4$$$, achieved at $$$i = 4$$$.

In the second test case, the gap value before applying any operations is $$$1$$$. We can show that applying any operation will increase this value, so the answer is $$$1$$$.