M. Max Minus Min
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given array $$$a$$$ of $$$n$$$ integers. You can perform the following operation at most once:

  • Choose any integers $$$1 \leq l \leq r \leq n$$$, and any integer $$$x$$$. Then, for each $$$l\leq i \leq r$$$, replace $$$a_i$$$ with $$$a_i + x$$$.

Find the smallest possible value of $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$ you can get after performing this operation at most once.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$)  — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)  — elements of the array.

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

Output

For each test case, in the first line output a single integer  — the smallest possible value of $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$ you can get after performing this operation at most once.

Example
Input
4
3
42 42 42
4
1 2 2 1
5
1 100 1 100 1
6
1 2 3 4 5 6
Output
0
0
99
2
Note

In the first test case, you don't need to make any operations, since $$$max - min = 0$$$ already.

In the second test case, you can choose $$$x = -1$$$, and segment $$$a[2:3]$$$. The array will become $$$[1, 1, 1, 1]$$$, with $$$max - min = 0$$$.

In the third test case, $$$max - min$$$ initially is $$$99$$$. Unfortunately, it's not possible to decrease this value with a single operation.

In the fourth test case, $$$max - min$$$ initially is $$$5$$$, but we can choose $$$x = 3$$$ and segment $$$a[1:3]$$$. The array will become $$$[4, 5, 6, 4, 5, 6]$$$, with $$$max - min = 2$$$.