Trong một trò chơi xây địa hình 2D, một khu vực ~A~ gồm ~n~ vùng liên tiếp có độ cao lần lượt là ~A_1, A_2, \dots, A_x, \dots, A_{n-1}, A_n~. Khu vực ~A~ được gọi là một ngọn núi khi sườn bên trái của nó tăng đơn điệu và sườn bên phải của nó giảm đơn điệu. Nghĩa là, khi ~A~ là ngọn núi với đỉnh núi là vùng có chiều cao ~A_x~, thì ~n~ vùng liên tiếp của ~A~ phải có độ cao đảm bảo ~A_1 \lt A_2 \lt \dots \lt A_x~ và ~A_x \gt \dots \gt A_{n-1} \gt A_n~ (~1 \lt x \lt n~). Hai vùng đầu tiên và cuối cùng của khu vực ~A~ không được là đỉnh núi.

Người chơi có thể tăng độ cao của các vùng để đắp ~A~ thành một ngọn núi. Với mỗi vùng ~A_i~ (~1 \leq i \leq n~), việc tăng độ cao lên ~1~ đơn vị sẽ tốn chi phí là ~1~ điểm.

Yêu cầu: Hãy viết chương trình tính chi phí tối thiểu để đắp khu vực ~A~ thành một ngọn núi.

Dữ liệu vào

Vào từ file văn bản DAPNUI.INP gồm ~2~ dòng:

• Dòng đầu chứa số nguyên ~n~ (~3 \leq n \leq 10^5~).
• Dòng tiếp theo gồm ~n~ số nguyên ~A_1, A_2, \dots, A_n~ (~0 \leq A_i \leq 10^9, 1 \leq i \leq n~).

Các số trên cùng một dòng cách nhau một khoảng trắng.

Kết quả ra

Ghi ra file văn bản DAPNUI.OUT:

• Một số nguyên duy nhất cho biết chi phí tối thiểu để đắp khu vực ~A~ thành một ngọn núi.

Ràng buộc

• Chương trình thực thi trong giới hạn ~1~ giây.
• ~60 \%~ số điểm của bài: ~3 \leq n \leq 10^3~.
• ~40 \%~ số điểm của bài: ~3 \leq n \leq 10^5~.

Ví dụ 1

Dữ liệu vào

5
1 1 1 1 1

Kết quả ra

4

Giải thích

Có nhiều phương án để đắp thành một ngọn núi.

• Có thể đắp được một ngọn núi với chiều cao: ~[1, 2, 3, 2, 1]~. Chi phí gồm: ~1~ điểm ở ~A_2~, ~2~ điểm ở ~A_3~ và ~1~ điểm ở ~A_4~. Tổng chi phí là ~4~ điểm. Đây là phương án có chi phí tối thiểu.
• Có thể đắp được một ngọn núi với chiều cao: ~[1, 4, 3, 2, 1]~. Tổng chi phí nhiều hơn, cụ thể là ~3 + 2 + 1 = 6~ điểm.

Ví dụ 2

Dữ liệu vào

6
3 4 5 6 5 1

Kết quả ra

0

Giải thích

• Vì ~A~ đã là một ngọn núi nên không cần đắp thêm. Chi phí là ~0~.