자리배열

디너 파티에 n명의 손님이 참석합니다. i 번째 손님의 키는 arr[i-1]인치 입니다.

손님은 1에서 n까지 번호가 매겨진 n 개의 좌석이 있는 원형 테이블 주위에 시계 방향으로 앉을 것입니다. 당신은 호스트로써 손님에게 가능한 좌석 순서 할당 방법을 선택합니다. 참고: n!개의 가능한 좌석 순서 할당방법이 있습니다

손님이 앉으면 양 옆의 손님들 사이의 어색함이 두 손님의 키 차이로 정의됩니다. 노트: 테이블이 원형이므로 좌석 1과 n은 서로 인접한 것으로 간주됩니다. 따라서 n 쌍의 인접 게스트가 있습니다.

좌석 배치의 전반적인 어색함은 인접한 손님들의 최대 어색함(최대 키 차이)로 결정됩니다. 가능한 최소한의 어색함(키 차이)을 만드는 좌석배치 함수를 작성하세요.

예제 1

입력

arr = [5, 10, 6, 8]  

출력

4

설명

만약 손님이 순열 [3, 1, 4, 2]에서 시계 방향으로 테이블 주위에 (높이 [6, 5, 8, 10], 순서대로) 앉는다면, 인접한 손님 쌍 사이에는 네 가지 키 차이 |6 - 5| = 1, |5 - 8| = 3, |8 - 10| = 2 및 |10 - 6| = 4가 있게 되고, 최대 키 차이는 4가 됩니다. 이보다 더 작은 최대 키 차이를 찾는 것은 불가능합니다.