Như đã biết thời gian để thực hiện việc tính tổng của hai số nguyên dương trên máy tính là phụ thuộc vào độ lớn của chúng. Để đơn giản ta coi rằng để cộng hai số nguyên dương ~a~ và ~b~ ta phải trả chi phí thời gian có giá trị bằng ~5~% giá trị của tổng hai số này (~a + b~). Giả sử ta cần phải tính tổng của ~N~ số nguyên dương cho trước. Dễ thấy là có nhiều cách tổ chức thực hiện công việc tính toán này, mỗi cách đòi hỏi chi phí thời gian nhất định. Chẳng hạn như cần tính tổng các số ~10, 11, 12, 13~. Ta có thể lần lượt thực hiện: Cộng ~10~ và ~11~ (mất chi phí ~1.05~), kết quả thu được đem cộng với ~12~ (mất chi phí ~1.65~), và cuối cùng cộng với 13 (mất chi phí ~2.3~). Tổng chi phí theo cách thực hiện này là ~5~. Một cách thực hiện khác là: Cộng ~10~ và ~11~ (~1.05~), tiếp đến cộng ~12~ với ~13~ (mất chi phí ~1.25~), cuối cùng cộng hai kết quả thu được (mất chi phí ~2.3~). Như vậy chi phí tổng cộng theo cách thứ hai là ~4.6~.

Yêu cầu: Cho dãy gồm ~N~ số nguyên dương. Cần tìm cách tính tổng các số này với tổng chi phí thời gian là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \leq N \leq 15000)~.
• Trong các dòng tiếp theo ghi ~N~ số nguyên dương mà ta cần tính tổng, hai số liên tiếp được ghi cách nhau bởi ít nhất một dấu cách hoặc dấu xuống dòng. Các số có giá trị không vượt quá ~10^4~

Dữ liệu ra:

• Tổng chi phí theo cách thực hiện tính tổng tìm được. Kết quả được ghi với chính xác hai chữ số sau dấu chấm thập phân.

Ví dụ:

Input 1

4
10 11 12 13

Output 1

4.60

Input 2

2
1 2

Output 2

0.15

• Subtask 1: 30% số test có ~N \leq 7~
• Subtask 2: 30% số test có ~N \leq 1000~
• Subtask 3: Không có điều kiện gì thêm