Description

Little S recently bought a handheld gaming console that is powered by two AA batteries. To ensure he can play games for extended periods, he purchased many AA batteries from different manufacturers, which vary in quality and thus have different lifespans—some last 5 hours, while others may only last 3 hours.

Clearly, if he only has two batteries—one lasting 5 hours and the other 3 hours—he can only play for 3 hours, leaving the remaining charge of one battery unused. However, if he has more batteries, he can utilize them more efficiently. For example, with three batteries lasting 3, 3, and 5 hours, he could first use the two 3-hour batteries for half an hour, then replace one with the 5-hour battery. After another two and a half hours, he could swap the remaining battery with the one previously set aside (which still has 2.5 hours of charge left). This way, he can play for a total of 5.5 hours without any waste.

Given the number of batteries and their respective lifespans, your task is to devise a strategy to maximize the total usage time.

Input Format

The input contains multiple test cases. Each test case consists of two lines. The first line is an integer ( N ) (( 2 \leq N \leq 1000 )), representing the number of batteries. The second line contains ( N ) positive integers indicating the lifespans of the batteries.

Output Format

For each test case, output a single line with the maximum possible usage time, rounded to one decimal place.

2
3 5
3
3 3 5

3.0
5.5