• محدودیت زمان: ۶ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

The government of the “Linear” galaxy plans to redesign the public-transportation system in the galaxy. The Linear galaxy, which is very far away from our galaxy Milky Way, consists of $2^n + 1$ stars located on a single line. The $i$-th star in the galaxy is placed at position $x_i$ on the line assuming the origin of the line is the starting point of the galaxy. Thus, the distance between stars $i$ and $j$ equals $|x_i - x_j|$.

There are two types of transportation systems in the Linear galaxy, namely TRT and SRT.

Teleport Rapid Transit (TRT) is an advanced transportation system, by which one can be instantly teleported from one star to another one within the TRT network. However, due to limited equipment, TRT stations can be installed in only $2^{n-1} + 1$ stars.

In order to make the whole transportation network connected, one of the stars in the TRT network and all stars not being in TRT network (a total of $2^{n-1} + 1$ stars) must be connected via the traditional Spacecraft Rapid Transit (SRT) system. A standard SRT network over m stars is a cycle of length $m$ passing through each star exactly once. Interestingly, spacecrafts work more efficiently on longer flights. Therefore, the efficiency of an SRT network is defined as the minimum of its flight distances (i.e. distances between every two consecutive stars in the cycle).

Now, the government of the linear galaxy looks for an SRT network with the maximum efficiency constructed over $2^{n-1}+1$ of the stars.

ورودی

There are multiple test cases in the input. The first line of each test case contains a single integer $n$, where $2^n + 1$ is the number of stars in the Linear galaxy ($1 \leq n \leq 10$). The next line contains $2^n + 1$ distinct positive integers not exceeding $10^9$ denoting the position of stars. The input terminates with a line containing $0$ which should not be processed.

خروجی

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

مثال

ورودی نمونه ۱

1
1 2 3
2
11 10 30 12 20
0

خروجی نمونه ۱

2
10