Captain Akeno and the crew stopped at a floating mall to replenish the ships supply of toilet paper. As any normal girl does, the captain stopped at a shoe store, where they had two awesome deals. The deals are as follows:
- If you group two pairs of shoes, you get the cheaper one at a 50% DISCOUNT.
- If you group three pairs of shoes, you get the cheapest one for FREE.
Captain Akeno had already placed the pairs of shoes on the conveyor when she was told that she can only group adjacent pairs. The group of girls didn't have much money at hand, so they kindly ask you to tell them the minimum obtainable price.
The first line of input will contain the integer ~N~ (~1 \le N \le 10\,000~), the number of pairs of shoes.
The second line of input will contain ~N~ space-separated integers representing the prices of the pairs of shoes.
On the first line, you must print the smallest obtainable price with one decimal.
5 100 27 15 25 400