You are given array of integers. You can perform the following operation at most once:
Choose any integers 1 \leq l \leq r \leq n, and any integer . 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.
The first line contains a single integer (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 (1 \leq n \leq 2\cdot 10^5) — the length of the array.
The second line of each test case contains 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 over all test cases does not exceed 2\cdot 10^5.
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
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 . Unfortunately, it's not possible to decrease this value with a single operation.
In the fourth test case, max - min initially is , 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.