정부 지원금

우리나라의 두 대형 은행이 심각한 위기에 빠졌습니다. 두 은행을 각각 A 은행과 B 은행이라고 부르겠습니다(실명을 밝히면 은행이 무너질 수 있어 알려 드릴 수 없습니다).

위기를 해결하기 위해 정부가 두 은행에 나누어 줄 여러 개의 금융 지원 패키지를 준비했습니다. 단, 한 가지 중요한 조건이 있습니다. 패키지는 한 번에 하나씩 은행에 지급되며, 지급이 진행되는 매 순간 두 은행이 지금까지 받은 금액의 차이를 되도록 작게 유지해야 합니다. 그렇지 않으면 한 은행이 다른 은행보다 큰 우위를 점하게 됩니다.

패키지를 지급하는 순서와 각 패키지를 어느 은행에 줄지는 자유롭게 정할 수 있습니다. 어떤 순간에 두 은행이 받은 금액 차이의 절댓값을 그 순간의 "차이"라고 할 때, 전체 지급 과정에서 나타나는 가장 큰 차이를 최소로 만드는 것이 목표입니다.

예를 들어 값이 100000, 110000, 120000, 150000인 네 개의 패키지가 있다고 합시다. 어떤 방식으로 나누면 가장 큰 차이가 130000까지 커지지만, 더 좋은 방식에서는 가장 큰 차이를 100000으로 억제할 수 있습니다. 따라서 이 경우의 답은 100000입니다.

입력은 여러 개의 패키지 묶음으로 이루어져 있습니다. 각 묶음은 패키지의 개수인 양의 정수 $N$ 한 개가 적힌 줄로 시작합니다($1 \le N \le 50000$). 다음 줄에는 공백으로 구분된 $N$개의 양의 정수가 주어지며, 모두 100000 이상 199999 이하입니다. 이 값들은 각 패키지에 들어 있는 금액을 뜻합니다. 패키지는 어떤 순서로도 지급할 수 있으므로, 둘째 줄에 적힌 수의 순서는 중요하지 않습니다.

마지막 묶음 다음에는 정수 0 하나만 적힌 줄이 옵니다.

각 패키지 묶음마다, 지급 과정 전체에서 나타나는 가장 큰 차이를 최소로 만들었을 때의 그 최솟값을 한 줄에 하나씩 출력하세요.

즉, 패키지를 하나씩 두 은행에 나누어 주는 순서와 대상을 잘 정하여, 매 순간의 차이(두 은행이 받은 금액의 절댓값 차이) 중 가장 큰 값이 최소가 되도록 했을 때, 그 최소로 억제한 "가장 큰 차이"를 정수로 출력합니다.