마법 지팡이

옛사람들은 마법을 신적인 힘의 도움을 끌어내는 기술로 여겼습니다. 잘 알려진 이야기에서 한 무리의 마법사가 지팡이를 바닥에 던지자 지팡이가 살아 있는 뱀으로 변했고, 이에 맞서 던져진 또 다른 지팡이는 그 뱀들을 모두 삼켜 버리는 뱀이 되었다고 합니다.

이 문제에 필요한 마법은 오직 풀이뿐입니다. 여러 개의 곧은 마디(segment)가 이음매(joint)로 차례로 연결되어 하나의 사슬을 이루는 마법 지팡이가 주어집니다. 지팡이는 이음매에서만 접을 수 있습니다. 지팡이를 접어 연속한 마디들의 한 구간의 양 끝을 맞닿게 하면 그 구간이 하나의 다각형으로 닫힙니다.

지팡이로 동시에 여러 개의 다각형을 만들 수 있습니다. 단, 각 마디는 최대 한 개의 다각형에만 쓰이고, 마디들은 끝점에서만 서로 닿을 수 있으며, 지팡이는 이음매에서만 접히는 하나의 사슬이므로 각 다각형은 반드시 연속한 마디들로 이루어져야 합니다. 어떤 다각형에도 속하지 않는 마디는 그냥 접지 않고 둡니다.

변의 길이가 정해진 다각형이 가질 수 있는 최대 넓이는 원에 내접하는 다각형일 때 얻어집니다. 지팡이를 접어 만든 다각형들이 감쌀 수 있는 넓이의 합의 최댓값을 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 하나의 마법 지팡이를 나타냅니다. 각 테스트 케이스의 첫 줄에는 마디의 개수를 나타내는 정수 $n$ ($1 \le n \le 500$)이 주어집니다. 다음 줄에는 지팡이를 따라 나타나는 순서대로 마디의 길이 $S_1, S_2, \ldots, S_n$ ($1 \le S_i \le 1000$)이 정수로 주어집니다.

마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 오며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 Case k: A 형식의 한 줄을 출력합니다. 여기서 $k$는 테스트 케이스 번호(1부터 시작)이고, $A$는 감쌀 수 있는 넓이의 합의 최댓값을 소수점 아래 정확히 여섯 자리까지 나타낸 값입니다. 어떤 다각형도 만들 수 없으면 넓이는 0.000000입니다.