Khỉ ăn chuối

Xem PDF
Tác giả:
jumptozero
Dạng bài
Điểm: 1400 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(n\) cây tre được đánh số từ \(1\) đến \(n\) (theo thứ tự từ trái sang phải). Cây tre thứ \(i\) có chiều cao là \(h_i\). Và ở trên mỗi cây tre đều có một quả chuối.

Có một chú khỉ tên là Lucii muốn ăn hết tất cả các quả chuối ở trên tất cả các cây.

Bây giờ chú khỉ đó đang đứng ở gốc của cây tre thứ \(1\). Và trong một giây, chú khỉ đó chỉ có thể thực hiện được một trong các hành động sau :

  • Đi lên trên hoặc xuống dưới một đơn vị trên một cây tre

  • Ăn quả chuối trên đỉnh của cây tre hiện tại

  • Nhảy sang cây tre kế tiếp. Tức là, nếu Lucii đang ở độ cao \(q\) của cây thứ \(i(1\le i\le n-1)\), cô ta sẽ nhảy sang độ cao \(q\) của cây thứ \(i+1\). Hành động này chỉ xảy ra khi \(q>h_{i+1}\)

Nhiệm vụ của bạn là tính thời gian tối thiểu (bằng giây) để chú khỉ ăn hết tất cả các quả chuối.

Input

  • Dòng thứ nhất chứa số nguyên \(n(1\le n\le 10^5)\)

  • \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(h_i(1\le h_i\le 10^4)\)

Output

  • Thời gian tối thiểu cần tìm

Example

Test 1

Input 
2
6 3
Output 
12
Note

Giải thích: Ban đầu chú khỉ sẽ tồn \(6\)s để đi từ gốc lên đỉnh , sau đó tốn \(1\) s để ăn quả chuối. Tiếp theo chú khỉ sẽ tốn \(3\) s để tuột xuống độ cao \(3\), tiếp tục tốn \(1\) s để nhảy sang cây thứ \(2\) và tốn \(1\) s cuối cùng để ăn quả chuổi của cây thứ \(2\).

Như vậy tổng thời gian tối thiểu là : \(6+1+3+1+1=12\) s

Bình luận