리니어 은하

"리니어" 은하의 정부가 은하 전체의 대중교통망을 다시 설계한다. 우리 은하에서 아주 멀리 떨어진 리니어 은하는 한 직선 위에 놓인 별 $2^n + 1$개로 이루어진다. 직선의 원점을 은하의 출발점으로 잡으면 $i$번째 별은 위치 $x_i$에 있고, 별 $i$와 별 $j$ 사이의 거리는 $|x_i - x_j|$다.

리니어 은하의 교통 체계는 TRT와 SRT 두 가지다.

TRT(Teleport Rapid Transit)는 발달한 교통 체계로, TRT 망에 속한 별 사이를 즉시 순간이동한다. 장비가 모자라서 TRT 역은 별 $2^{n-1} + 1$개에만 설치할 수 있다.

교통망 전체를 연결하려면 TRT 망에 속한 별 하나와 TRT 망에 속하지 않은 별 전부, 모두 $2^{n-1} + 1$개의 별을 재래식 교통 체계인 SRT(Spacecraft Rapid Transit)로 이어야 한다. 별 $m$개를 잇는 표준 SRT 망은 각 별을 정확히 한 번씩 지나는 길이 $m$의 순환로다. 우주선은 비행 거리가 길수록 효율이 좋다. 그래서 SRT 망의 효율은 순환로에서 이웃한 두 별 사이의 비행 거리 중 최솟값으로 정의한다.

정부는 별 $2^{n-1} + 1$개 위에 세우는 SRT 망 가운데 효율이 가장 높은 것을 찾는다. 그 최대 효율을 구하라.

$n = 1$이면 SRT 망은 별 두 개를 지나고 두 별을 오가는 비행 하나만 있으므로, 효율은 두 별 사이의 거리다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 정수 $n$이 주어진다 ($1 \le n \le 10$). 리니어 은하의 별은 $2^n + 1$개다. 다음 줄에는 별의 위치를 나타내는, $10^9$ 이하의 서로 다른 양의 정수 $2^n + 1$개가 주어진다. 위치가 정렬된 순서로 주어진다는 보장은 없다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 가능한 모든 SRT/TRT 망 가운데 최대 효율을 정수 하나로 한 줄에 출력한다.