Linear Galaxy

Time limit2sMemory limit512 MB

Summary

Given 2^n + 1 points on a line, choose 2^(n-1) + 1 of them so that the minimum gap around their cyclic order is as large as possible.

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

Problem

The government of the "Linear" galaxy plans to redesign the public transportation system of the galaxy. The Linear galaxy lies very far from our own galaxy and consists of $2^n + 1$ stars placed on a single line. Taking the origin of the line as the starting point of the galaxy, the $i$ -th star sits at position $x_i$ , so the distance between stars $i$ and $j$ is $|x_i - x_j|$ .

The Linear galaxy has two transportation systems, TRT and SRT.

Teleport Rapid Transit (TRT) is the advanced one. A traveler is teleported instantly from one star of the TRT network to another star of that network. Equipment is limited, so TRT stations can be installed in only $2^{n-1} + 1$ stars.

To make the whole transportation network connected, one star of the TRT network together with every star outside the TRT network, $2^{n-1} + 1$ stars in total, must be joined by the traditional Spacecraft Rapid Transit (SRT) system. A standard SRT network over $m$ stars is a cycle of length $m$ that passes through each of those stars exactly once. Spacecrafts work more efficiently on longer flights, so the efficiency of an SRT network is the minimum of its flight distances, that is, the smallest distance between two consecutive stars of the cycle.

The government looks for the SRT network of maximum efficiency built over $2^{n-1} + 1$ of the stars. Report that maximum efficiency.

When $n = 1$ , the SRT network passes through 2 stars and has a single flight running back and forth between them, so its efficiency is the distance between those 2 stars.

Input

The input holds several test cases. The first line of each test case contains one integer $n$ ( $1 \le n \le 10$ ), and the Linear galaxy then has $2^n + 1$ stars. The next line contains $2^n + 1$ distinct positive integers not exceeding $10^9$ , the positions of the stars. The positions are not necessarily sorted. The input ends with a line containing 0, which must not be processed.

Output

For each test case, print one line with a single integer, the maximum efficiency among all possible SRT/TRT networks.

Examples6

Example 1
Input
```
1
1 2 3
2
11 10 30 12 20
0
```
Expected output
```
2
10
```

Example 2

Input

1
1000000000 1 500000000
1
4 9 1
0

Expected output

999999999
8

Example 3
Input
```
2
1 2 3 4 5
0
```
Expected output
```
2
```
Example 4
Input
```
2
1 2 3 4 1000000000
0
```
Expected output
```
3
```
Example 5
Input
```
3
1 2 3 4 5 6 7 8 9
0
```
Expected output
```
4
```

Example 6

Input

1
7 1000000000 3
2
100 1 50 999 500
3
712 81 499 459 574 709 578 57 674
4
635810045 68885204 357697771 869198710 742092701 576430954 534273889 841459442 48006128 485576225 978959697 547326355 113342467 509296116 473035042 72657848 160694867
0

Expected output