원판 배치

$n$개의 원판을 평면에 놓아 각 원판이 위쪽에서 x축에 닿고, 두 원판이 겹치지 않도록 합니다. 유효한 배치에서 각 원판은 가장 낮은 점에서 x축에 닿으며, 이 점을 원판의 바닥점이라고 합니다. 바닥점들이 원판에 왼쪽에서 오른쪽으로 가는 선형 순서를 정합니다. 선형 인스턴스는 원판들의 집합 $\{D_1, D_2, \ldots, D_n\}$으로, 원판들의 모든 순서 $\sigma$, 즉 $D_{\sigma(1)} D_{\sigma(2)} \ldots D_{\sigma(n)}$에 대해 배치가 존재하는 집합입니다. 이 배치에서 $D_{\sigma(i)}$는 $D_{\sigma(i-1)}$과 $D_{\sigma(i+1)}$에만 닿습니다. 다만 $D_{\sigma(1)}$은 $D_{\sigma(2)}$에만, $D_{\sigma(n)}$은 $D_{\sigma(n-1)}$에만 닿습니다. 그림 C.1은 선형 인스턴스이고, 그림 C.2는 선형 인스턴스가 아닌 예입니다. 가장 큰 반지름과 가장 작은 반지름의 비가 4보다 작으면 원판들은 선형 인스턴스를 이루므로, 입력은 모두 이 조건을 만족합니다. 주어진 선형 인스턴스에서 원판들의 가장 왼쪽 점과 가장 오른쪽 점 사이의 수평 거리가 최소가 되는 유효한 배치를 찾습니다(그림 C.3).

첫 줄에 원판의 개수를 나타내는 정수 $n$ ($1 \le n \le 1{,}000$)이 주어집니다. 둘째 줄에는 각 원판의 반지름 $a$ ($1 \le a \le 1{,}000{,}000$)인 정수 $n$개가 주어집니다. 가장 큰 반지름과 가장 작은 반지름의 비는 4보다 작습니다.

모든 유효한 배치에서 원판의 가장 왼쪽 점과 가장 오른쪽 점 사이 수평 거리의 최솟값 $OPT$를 실수 $z$로 한 줄에 출력합니다. $z$는 정수부, 소수점, 소수부의 형식으로 출력하며, $OPT - 10^{-5} < z < OPT + 10^{-5}$를 만족해야 합니다.