Cờ nhảy (jumpf.*)

Cờ nhảy là trò chơi một người có quy tắc như sau:

• Trò chơi diễn ra trên một dãy n ô vuông xếp thành một hàng, các ô được đánh số \(1,\ 2,\ \ldots,\ n\) từ trái sang phải.

• Ban đầu quân cờ ở ô 1, nhiệm vụ của người chơi là đưa quân cờ đến ô \(n\).

• Trong lượt đi đầu tiên, người chơi phải đưa quân cờ đến ô 2 (thực hiện bước nhảy độ dài 1).

• Trong các lượt đi sau đó, nếu đưa quân cờ tiến lên thì độ dài bước nhảy phải tăng lên 1, còn nếu đưa quân cờ lùi lại thì độ dài bước nhảy phải giữ nguyên.

• Phí phải trả khi đưa quân cờ nhảy vào ô \(i\) là \(a_{i}\). Chú ý rằng việc quân cờ ở ô 1 lúc xuất phát là không phải trả phí.

Yêu cầu: Hãy xác định tổng phí phải trả nhỏ nhất để đưa được quân cờ đến ô \(n\).

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\ (2\ \leq \ n\ \leq \ 1000)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1\ \leq \ a_{i}\ \leq \ 500,\ 1\ \leq \ i\ \leq \ n)\).

Kết quả: Ghi một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Input	Output
6 1 2 3 4 5 6	12
8 2 3 4 3 1 6 1 4	14

Ràng buộc:

• 40% số test với \(2\ \leq \ n\ \leq \ 20\)

• 60% số test với \(2\ \leq \ n\ \leq \ 1000\)