대나무집2 timer 1s memory 128MB

진흥이는 N개의 작은 대나무들을 엮어서 기르고 있던 강아지의 집을 지어주려고 한다.

일단 대나무들을 일렬로 세워놓은 후 맨 앞과 맨 끝을 이어서 둥그렇게 엮어서 울타리를 완성한 후에 중간에 문을 낼 예정이다.

대나무들의 길이가 들쭉날쭉하여 크기를 맞추고는 싶지만 진흥이가 가지고 있는 작은 커터칼로는 단 한 개의 대나무만을 잘라낼 수 있다.

이웃 대나무끼리의 길이의 차가 너무 많은 차이가 날 경우 제대로 엮을 수가 없어서 튼튼한 울타리를 만들 수가 없다. 

7개의 대나무의 길이가 각각 “5 9 3 4 7 6 10” 이라면 이것을 순서를 바꾸지 않고 그대로 엮을 경우 이웃한 대나무의 차가 가장 큰 곳은 맨 앞의 5와 마지막에 있는 10의 차인 5이다.

“7 5 3 4 6 9 10” 과 같이 순서를 바꾸게 되면 이웃한 대나무의 차가 가장 큰 곳은 6과 9 와 차 또는 마지막 10과 맨 앞의 7의 차인 3이 되고 이 경우가 차의 최대값이 최소인 경우가 된다. 만약 길이가 10인 대나무를 잘라서 8로 만든 후 “7 5 3 4 6 8 9” 와 같이 재배치를 하면 이웃한 대나무의 차가 최대인 값은 2가 된다.

주어진 대나무와 대나무 한 개를 잘라낼 수 있는 커터칼을 이용하여 이웃 대나무 간의 길이 차이가 최대인 값이 최소가 되도록 배치했을 때 차이가 최대인 값을 출력하는 프로그램을 작성하라.​