Магические палки
Магия считалась всеми древними народами методом, при помощи которого можно добиться помощи у божественных сил. В одной известной истории группа колдунов бросили свои трости на пол, где они чудесным образом превратились в живых змей. В ответ другой человек бросил палку на пол, где она превратился в змею, которая затем истребила змей магов!
Единственная магия, которая нужна в задаче - это ее решение. У вас имеется волшебная палочка, состоящая из нескольких прямых отрезков и шарниров, позволяющих ей складываться. В зависимости от длин отрезков и метода их складывания, можно получить разное количество многоугольников. Вам следует найти максимальную площадь, которую могут ограничить образованные подобным образом многоугольники. Каждый отрезок должен входить в не более чем один многоугольник. Отрезки могут соприкасаться только своими концами. Например, представленная ниже палка имеет пять отрезков и четыре шарнира. Она может быть сложена для получения многоугольника, как показано на рисунке справа.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест описывает магическую палку. Первая строка каждого теста задает количество n (1 ≤ n ≤ 500) отрезков в магической палке. Следующая строка содержит n целых чисел S_1, S_2, ..., S_n (1 ≤ S_i ≤ 1000) - длины отрезков в том же порядке, в котором они расположены на палке.
Последний тест завершается строкой, содержащей единственный ноль.
Выходные данные
Для каждого теста вывести его номер и максимально возможную площадь замкнутой области, которую можно получить, сгибая магическую палку в заданных местах. Допускаются ошибки округления не более 10^{-4}.
Формат выходных данных указан в примере.