리니어 은하

시간 제한2초메모리 제한512 MB

요약

직선 위의 2^n + 1개 점 중 2^(n-1) + 1개를 골라, 고른 점들을 순환 순서로 이었을 때 인접한 점 사이 최소 거리를 최대화하는 값을 구한다.

난이도: 보통10점 중 7점
유형: 정렬, 그리디, 조합론
정답자: 아직 제출이 없습니다

문제

"리니어" 은하의 정부가 은하 전체의 대중교통망을 다시 설계한다. 우리 은하에서 아주 멀리 떨어진 리니어 은하는 한 직선 위에 놓인 별 $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 망 가운데 최대 효율을 정수 하나로 한 줄에 출력한다.

예제6

예제 1
입력
```
1
1 2 3
2
11 10 30 12 20
0
```
예상 출력
```
2
10
```

예제 2

입력

1
1000000000 1 500000000
1
4 9 1
0

예상 출력

999999999
8

예제 3
입력
```
2
1 2 3 4 5
0
```
예상 출력
```
2
```
예제 4
입력
```
2
1 2 3 4 1000000000
0
```
예상 출력
```
3
```
예제 5
입력
```
3
1 2 3 4 5 6 7 8 9
0
```
예상 출력
```
4
```

예제 6

입력

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

예상 출력