키 배치

N명의 사람이 원형 테이블에 둘러앉으려고 한다. 각 사람은 자신과 이웃한 사람의 키 차이가 너무 커지는 것을 원하지 않는다.

한 배치의 불편도는 원형으로 인접한 모든 두 사람의 키 차이 중 최댓값이다. 주어진 N명의 키를 한 줄로 나열했을 때, 그 순서를 시계 방향 배치라고 보자.

불편도가 최소가 되는 시계 방향 배치를 출력하라. 가능한 배치가 여러 개라면, 출력되는 수열이 사전순으로 가장 앞서는 배치를 출력한다.

첫째 줄에 사람의 수 N이 주어진다. N은 3 이상 50 이하이다.

둘째 줄에 각 사람의 키 N개가 주어진다. 각 키는 1000 이하의 자연수이다.

불편도가 최소인 시계 방향 배치 하나를 첫째 줄에 공백으로 구분해 출력한다. 그런 배치가 여러 개라면 사전순으로 가장 앞서는 수열을 출력한다.