Nhằm kích cầu tiêu dùng, siêu thị LDN đã đề ra chiến dịch khuyến mãi vô cùng hấp dẫn.

Siêu thị sẽ trưng bày \(n\) món hàng thành một dãy. Lần lượt mỗi món hàng theo thứ tự trái sang phải có giá trị nguyên dương \(a_{1}, a_{2}, \dots, a_{n}\).

Khách hàng có thể chọn một số món hàng liên tiếp nhau. Cụ thể, khách hàng có thể chọn một dãy các món hàng \(a_{l}, a_{l + 1}, \dots, a_{r - 1}, a_{r}\) \((1 \leq l \leq r \le n)\).

Sau khi chọn, khách hàng có thể sở hữu toàn bộ \(n\) món hàng được trưng bày với mức giá là chênh lệch giữa tổng giá trị các món hàng được chọn và tổng giá trị các món hàng còn lại.

Hãy lập trình để tìm số tiền nhỏ nhất mà khách hàng cần bỏ ra để sở hữu \(n\) món hàng trên.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \times 10^{6})\) - số lượng món hàng được trưng bày.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \dots, a_{n}\) \((1 \leq a_{i} \leq 10^{9}, 1 \leq i \leq n)\) - giá trị của từng món hàng theo thứ tự trái sang phải.

Output

• In ra số tiền nhỏ nhất để sở hữu được \(n\) món hàng.

Constraints

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le n \le 5000\).
• Subtask \(3\) (\(30\%\) số điểm): \(1 \le n \le 5 \times 10^{5}\).
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Examples

5
1 2 3 4 5

1