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