현대모비스에서 개발한 자율주행을 이용한 레이싱 대회가 열렸습니다. 당신은 관람객들이 레이싱 대회를 재밌게 즐길 수 있도록 레이싱 경기장을 설계하려고 합니다.

레이싱 경기장은 n개의 지점으로 구성됩니다. 각 지점의 높이는 정해져 있지만, 그 순서는 자유롭게 바꿀 수 있습니다. 당신의 목표는 이웃한 지점끼리의 높이 차이의 최솟값이 최대가 되도록 높이 순서를 정하는 것입니다.

예를 들어 n이 3이고 세 지점의 높이가 각각 1, 5, 8인 경우를 생각해 봅시다.

• 높이를 [1, 5, 8] 순서로 배치하면 1번과 2번 지점의 높이 차이는 4, 2번과 3번 지점의 높이 차이는 3이므로 높이 차이의 최솟값은 3입니다.
• 높이를 [5, 1, 8] 순서로 배치하면 1번과 2번 지점의 높이 차이는 4, 2번과 3번 지점의 높이 차이는 7이므로 높이 차이의 최솟값은 4입니다.

높이 차이의 최솟값을 4보다 크게 만드는 방법은 없습니다.

지점 n개의 높이를 담은 1차원 정수 배열 heights가 매개변수로 주어집니다. 높이 차이의 최솟값이 최대가 되도록 레이싱 경기장을 설계했을 때의 높이 차이의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 2 ≤ heights의 길이 = n ≤ 200,000
  • 1 ≤ heights의 원소 ≤ 10⁹

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

높이를 [4, 11, 6, 11] 순서로 배치하면 높이 차이의 최솟값이 5입니다. 높이 차이의 최솟값을 5보다 크게 만드는 방법은 없습니다.

따라서 5를 return 하면 됩니다.

입출력 예 #3

높이를 어떻게 배치하더라도 높이가 9인 지점 두 개가 이웃하게 됩니다. 따라서 높이 차이의 최솟값은 항상 0입니다.

따라서 0을 return 하면 됩니다.