Nikola

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Nikola đứng ở ô 1 trong dãy $N$ ô và lần nhảy đầu buộc tới ô 2. Nếu nhảy tiến, độ dài phải lớn hơn bước trước đúng 1; nếu nhảy lùi, độ dài bằng bước trước. Mỗi lần vào một ô phải trả phí. Hãy tới ô $N$ với chi phí nhỏ nhất.

Input

Dòng đầu chứa $N$. Sau đó có $N$ dòng phí vào các ô từ 1 đến $N$.

Output

In chi phí nhỏ nhất.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

6
1
2
3
4
5
6

Output

13

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.