Đua xe đạp
View as PDFTrong cuộc đua xe đạp địa hình vô địch thế giới, các tay đua phải vượt qua nhiều dạng địa hình khác nhau. Đặc biệt lần này ban tổ chức đưa vào một dạng địa hình mới: đua trên những bậc thang. Đường đua gồm n bậc thang liên tiếp nhau được đánh số từ 1 đến n, bậc thang thứ i có độ cao ~a_i~. Trên đường đua xuất hiện các lòng chảo là những bậc thang liên tiếp nhau, mỗi lòng chảo được mô tả bằng bộ ba l,m,r (l<m<r;~a\_l~>~a_m~<~a_r~) sao cho độ cao các bậc thang giảm dần từ ~a_l~ đến ~a_m~ rồi tăng dần từ ~a_m~ đến ~a_r~. </p>
Đây là một cuộc đua khó khăn nên tất cả các tay đua đều có chiến thuật: trên mỗi lòng chảo l,m,r, khi đang ở bậc thang l tay đua sẽ cho xe đạp tự chạy đến bậc thang thứ k sao cho ~a_k~ lớn nhất và ~a_k~ ≤ ~a_l~ (m ≤ k ≤ r) rồi đạp xe chạy từ bậc thang thứ k đến bậc thang thứ r (nếu k < r).
Trong ví dụ trên gồm 10 bậc thang và có 2 lòng chảo là (1,2,4) và (4,7,10). Trong lòng chảo (4,7,10), tay đua sẽ cho xe tự chạy từ bậc thang thứ 4 đến bậc thang thứ 9, rồi đạp xe chạy đến bậc thang thứ 10.
Yêu cầu:
Hãy cho biết các tay đua cần ít nhất bao nhiêu đơn vị sức mạnh để hoàn thành cuộc đua. Biết rằng mỗi tay đua cần ~a_{(i+1)}~-~a_i~ đơn vị sức mạnh để đạp xe từ bậc thang thứ i đến bậc thang thứ i+1. Mỗi bậc thang đều thuộc ít nhất một lòng chảo.
Dữ liệu vào:
- Dòng đầu tiên ghi số nguyên dương n
- Dòng thứ 2 ghi n số nguyên lần lượt là ~a_1~,~a_2~,…,~a_n~
Kết quả:
Một số nguyên duy nhất là kết quả của bài toán.
Ví dụ:
INPUT
10
7 4 6 7 6 5 3 4 6 8
OUTPUT
2
Giới hạn:
- 3 ≤ n ≤ ~10^6~
- 0 < ~a_i~ ≤ ~10^9~ (i=1...n)
Comments
my life, my choice
my life, my colour