Jumping Across Logs

Interview

Time limit1sMemory limit256 MB

Summary

Arrange the given log heights in a circle to minimize the largest height gap between neighbors.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Namgyu likes to stand logs upright and jump from one to the next. He stands N logs in a circle and jumps only to a log next to the one he is on, so he wants to arrange the logs so that the height difference between neighbours stays as small as possible.

The difficulty of the circle is the largest height difference between two neighbouring logs. Suppose the five logs have heights 2, 4, 5, 7 and 9. Standing them in the order $[2, 9, 7, 4, 5]$ also puts the first log next to the last one, so the log of height 2 touches the log of height 5. That arrangement has difficulty $|2 - 9| = 7$ . The better arrangement $[2, 5, 9, 7, 4]$ has difficulty $|5 - 9| = 4$ , and no arrangement has a lower difficulty, so 4 is the answer.

Given the heights of the logs, find the smallest difficulty of any circular arrangement.

Input

The first line contains the number of test cases T.

Each test case takes two lines. The first line contains the number of logs N ( $5 \le N \le 10000$ ). The second line contains the N log heights $L_i$ ( $1 \le L_i \le 100000$ ), separated by spaces.

Output

For each test case, print the smallest difficulty on its own line.

Examples5

Example 1

Input

3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

Expected output

1
4
0

Example 2
Input
```
1
5
1 2 3 4 5
```
Expected output
```
2
```
Example 3
Input
```
1
5
1 100000 1 50000 100000
```
Expected output
```
99999
```
Example 4
Input
```
1
6
100000 4 2 5 3 1
```
Expected output
```
99996
```

Example 5

Input

2
5
7 7 7 7 8
9
1 3 6 10 15 21 28 36 45

Expected output

1
17