Trong 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
Đâ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
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
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à
, ,…,
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 ≤
- 0 <
≤ (i=1...n)
Comments
my life, my choice
my life, my colour