An dự định bay tới Đà Lạt, nhưng vì nhầm chuyến nên lại đáp xuống sân bay ở Sa Pa. Cậu nhanh chóng đặt một phòng khách sạn trong thị trấn và phải đi bộ tới đó trong đêm lạnh. Khách sạn của An nằm ở cuối một con đường dài ~N~ mét. Trên con đường này có ~N-1~ cửa hàng quần áo; cửa hàng thứ ~i~ nằm cách sân bay đúng ~i~ mét.

An chỉ đi theo hướng từ sân bay tới khách sạn. Khi đi ngang qua cửa hàng thứ ~i~, cậu có thể chọn một trong ba cách:

• tiếp tục đi mà không vào cửa hàng;

• vào cửa hàng để sưởi ấm, trả ~1~ đồng và không mua gì;

• vào cửa hàng, trả ~1~ đồng và mua thêm một lớp áo với giá ~A_i~ đồng.

An muốn tránh bị lạnh, nên trong suốt hành trình, cậu không được đi liên tiếp số mét nhiều hơn số lớp áo đang mặc mà không vào một cửa hàng nào. Ban đầu, khi vừa tới sân bay, An đang mặc đúng một lớp áo.

Hãy tính số tiền ít nhất An cần trả để tới được khách sạn.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 10^5)~: độ dài con đường.

• Dòng thứ hai chứa ~N-1~ số nguyên ~A_1, A_2, \dots, A_{N-1}~ ~(1 \le A_i \le 10^9)~: giá mua thêm một lớp áo ở từng cửa hàng.

Output

Ghi ra một số nguyên duy nhất là số tiền ít nhất An cần trả.

Scoring

Sample Input 1

8
5 1 9 1 9 9 9

Sample Output 1

5

Sample Input 2

10
6 4 2 7 1 8 3 9 5

Sample Output 2

8

Notes

Trong ví dụ thứ nhất, An có thể vào cửa hàng thứ nhất để sưởi ấm, mua thêm một lớp áo ở cửa hàng thứ hai, rồi vào cửa hàng thứ tư và thứ sáu để sưởi ấm. Tổng chi phí là ~1 + (1+1) + 1 + 1 = 5~.

Trong ví dụ thứ hai, An có thể vào cửa hàng thứ nhất và thứ hai để sưởi ấm, mua thêm áo ở cửa hàng thứ ba và thứ năm, rồi vào cửa hàng thứ bảy để sưởi ấm. Tổng chi phí là ~1 + 1 + (1+2) + (1+1) + 1 = 8~.