Thực hiện nhiệm vụ cấp trên giao, đội A lên đường làm nhiệm vụ trong đêm. Đội xuất phát từ trạm dã chiến tới vị trí tập kết mới có tổng độ dài ~N~ Km. Thời tiết về đêm rất lạnh nên trên tuyến đường này cần có ~N - 1~ trạm hậu cần dã chiến nằm ở các mốc ~1~ Km, ~2~ Km, ~\dots~, ~(N - 1)~ Km.

Ban đầu, đội xuất phát tại mốc ~0~ Km và các thành viên trong đội được trang bị một lớp áo ấm. Để tránh bị hạ thân nhiệt trong suốt hành trình, đội không được phép đi số kilomet liên tiếp nhiều hơn số lớp áo đang mặc. Vì vậy, đội có thể ghé vào một số trạm hậu cần, khi ghé vào trạm hậu cần thứ ~i~, đội trưởng bắt buộc chọn một trong ~2~ phương án:

• Phương án ~1~: Sưởi ấm tốn chi phí ~1~ đồng. Sau đó, đội có thể tiếp tục đi được số kilomet bằng số lớp áo được trang bị trước đó;

• Phương án ~2~: Sưởi ấm và trang bị thêm một lớp áo thì chi phí tại trạm là ~1 + c_i~ đồng. Sau đó, đội có thể tiếp tục đi được số kilomet bằng số lớp áo được trang bị tới thời điểm hiện tại.

Yêu cầu: Hãy tính tổng chi phí hậu cần ít nhất để đội A vượt qua tuyến đường trên.

Input

• Dòng thứ nhất chứa số nguyên ~N~ ~(2 \le N \le 10^5)~ là độ dài tuyến đường hành quân (Km).

• Dòng thứ hai chứa ~N - 1~ số nguyên không âm ~c_1, c_2, \dots, c_{N-1}~ ~(1 \le c_i \le 10^9)~ lần lượt là giá một lớp áo ấm tại các trạm từ ~1~ đến ~N - 1~.

Output

Ghi ra một số nguyên duy nhất là tổng chi phí hậu cần ít nhất.

Scoring

Sample Input 1

8
5 1 9 1 9 9 9

Sample Output 1

5

Notes

• Mốc ~0~ Km: Các thành viên được trang bị một lớp áo. Ghé trạm ~1~ sưởi ấm tốn chi phí ~1~ đồng. Ghé trạm ~2~ sưởi ấm và trang bị thêm một lớp áo tốn chi phí thêm ~2~ đồng (số áo hiện tại là ~2~). Đi tiếp ~2~ km, ghé trạm ~4~ sưởi ấm tốn chi phí thêm ~1~ đồng. Đi tiếp ~2~ km, ghé trạm ~6~ sưởi ấm tốn chi phí thêm ~1~ đồng. Đi tiếp ~2~ km, tới vị trí khảo sát mới (mốc ~8~ Km). Tổng chi phí: ~1 + 2 + 1 + 1 = 5~.