Khi dạy về thuật toán, Nam thường tổ chức các trò chơi, dưới đây là một trò chơi có nhiều chiến thuật chơi tương ứng với nhiều chiến lược thiết kế thuật toán.

Ban đầu, Nam tạo một dãy số nguyên dương \(a_1, a_2, ..., a_n\) tương ứng với \(n\) lượt chọn. Một người chơi sẽ thực hiện đúng \(n\) lượt chọn, với lượt chọn thứ \(i\) \((1 \le i \le n)\) người chơi sẽ chọn số nguyên \(b_i\) mà \(b_i \le a_i\). Kết thúc \(n\) lượt chọn nếu tồn tại mọi \(l, r\) mà \(1 \le l \lt i \lt r \le n\) và \(b_l \gt b_i \lt b_r\), thì người chơi giành chiến thắng và nhận được số kẹo là tổng giá trị \(b_i\) ở các lượt, ngược lại, người chơi sẽ không nhận được kẹo.

Yêu cầu

• Cho dãy số nguyên dương \(a_1, a_2, ..., a_n\), hãy giúp Nam tính số kẹo ít nhất cần chuẩn bị để trong mọi trường hợp đều đủ số kẹo cho một người chơi.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên \(n\).
• Dòng tiếp theo chứa \(n\) số nguyên dương cách nhau bởi dấu cách \(a_1, a_2, ..., a_n\) \((a_i \le 10^9)\).

Kết quả:

• Ghi ra thiết bị ra chuẩn một số nguyên là số kẹo ít nhất mà Nam cần chuẩn bị để trong mọi trường hợp đều đủ số kẹo cho một người chơi.

Input 1

4
1 2 1 2

Output 1

5

Giới hạn:

• Subtask 1 (60% số điểm): \(n \le 5000\);
• Subtask 2 (40% số điểm): \(n \le 5 \times 10^5\).