Các bé học sinh trường mầm non SuperKids tò rò say mê với các trò chơi đòi hỏi tư duy thuật toán chuyên nghiệp. Nhân dịp đến thăm trường, giáo sư X bày ra một trò chơi cho các bạn nhỏ tại đây.

Ban đầu, người chơi được cho \(n\) thùng nước đánh số từ \(1\) tới \(n\). Thùng thứ \(i\) có \(a_i\) lít nước. Người chơi được quyền múc một lượng nước bất kỳ từ một thùng chuyển sang thùng liền sau (chuyển từ thùng \(i\) sang thùng \(i + 1\) với \(i\) tùy chọn thỏa mãn \(1 \leq i < n\)). Năng lượng tiêu tốn cho thao tác này đúng bằng lượng nước được chuyển (có thể không phải là số nguyên).

Nhiệm vụ của người chơi là phải làm cho lượng nước trong các thùng sắp xếp thứ tự không giảm, tức là:

Yêu cầu

Hãy tìm phương án chơi sao cho tổng năng lượng tiêu tốn là ít nhất.

Input

• Dòng 1 chứa số nguyên dương \(n \leq 10^6\)
• Dòng 2 chứa \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) (với: \(a_i \leq 10^6\)) cách nhau bởi dấu cách

Output

• Ghi ra một số thực duy nhất với 1 chữ số sau dấu chấm thập phân là tổng năng lượng tiêu tốn nếu các bé chơi theo phương án của bạn

Example

6
1 3 0 0 3 0

4.5