Question
Range Minimize

Ram is given an array A containing N integers. Ram can delete at most two of its elements.
Find the minimum possible value of (max(A) − min(A)) (in other words, the range of A) after the deletions.

Input
The first line of the input contains a single integer T, denoting the number of test cases.
Each test case contains two lines of input.
- The first line of each test case contains a single integer N, denoting the length of an array.
- The second line contains N space-separated integers A1, A2, A3, ..., AN.

Constraints
1 ≤ T ≤ 105
3 ≤ N ≤ 2x105
1 ≤ Ai ≤ 109
Note: The sum of N over all test cases won't exceed 2x105
Output
For each test case, output on a new line the minimum possible value of max(A)−min(A) after at most two deletions.
Example
Sample Input
2
3
2 3 1
5
1 10000 10 100 1000
Sample Output
0
99
Explanation
Test case 1: Delete 1 and 2 to make the array A = [3]. max(A) − min(A) = 0, which is the best we can do.
Test case 2: Delete A2 = 10000 and A5 = 1000 to obtain A = [1, 10, 100], for which max(A) - min(A) = 90

Online