성간 무역

Q가 자신의 알 수 없는 시험을 통과한 시스코 사령관에게 보기 드문 보상을 내렸다. 베이조 웜홀의 양쪽 끝을 원하는 곳으로 옮길 기회다. 물론 딥스페이스 나인도 웜홀을 따라 함께 움직인다. 사령관이 이전 계획을 공모하자, 여러 상인이 교역으로 잘 알려진 행성 사이의 이동 시간을 줄이려고 웜홀의 양 끝을 알려진 우주 안에 두기를 원했다. 이 행성 중 두 행성 사이 거리의 최댓값이 가장 작아지도록 웜홀의 두 끝을 놓는 방법을 찾아라.

문제에 등장하는 행성은 모두 하나의 직선 위에 있고, 웜홀이 없다면 두 행성 사이의 거리는 그냥 직선 거리다. 웜홀이 생기면 여행자는 한 행성에서 웜홀의 한쪽 끝까지 곧장 간 다음 반대쪽 끝에서 목적지 행성까지 곧장 가는 경로도 고를 수 있다. 웜홀의 두 끝 사이를 지나는 데는 시간이 걸리지 않으므로, 이때 이동 거리는 두 구간 거리의 합이다. 웜홀의 끝이 두 행성 사이에 놓여 있더라도 여행자는 웜홀을 쓰지 않고 그냥 갈 수 있다. 웜홀의 끝은 어떤 행성에든 원하는 만큼 가깝게 놓을 수 있어서, 그 행성에서 웜홀까지의 거리를 사실상 0으로 만들 수 있다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 50$)가 주어진다.

각 테스트 케이스의 첫 줄에는 행성의 수 $N$ ($2 \le N \le 4000$)이 주어진다. 이어지는 $N$개의 줄에는 행성 $i$의 위치 $x_i$ ($-10^9 \le x_i \le 10^9$)가 한 줄에 하나씩 정수로 주어진다. 모든 행성은 x축 위의 점이고, 위치가 같은 두 행성은 없다.

각 테스트 케이스마다 두 행성 사이 거리의 최댓값이 가장 작아지도록 웜홀을 놓았을 때의 그 최댓값을 한 줄에 출력한다. 이 값이 정수가 아니면 올림해서 출력한다.

행성의 위치는 정수로 주어지지만 웜홀 끝의 좌표는 정수가 아닐 수 있다.