니콜라의 점프

니콜라는 일렬로 놓인 N개의 발판 위를 이동한다. 발판은 왼쪽부터 1번부터 N번까지 번호가 붙어 있다.

니콜라는 1번 발판에서 시작하며, 첫 번째 이동은 반드시 2번 발판으로 가는 길이 1의 점프이다. 이후에는 마지막으로 앞으로 점프했던 거리를 기준으로 다음 규칙을 따른다.

• 앞으로 점프할 때는 마지막 앞으로 점프한 거리보다 1칸 더 멀리 뛴다.
• 뒤로 점프할 때는 마지막 앞으로 점프한 거리만큼 뛴다. 뒤로 점프해도 이 기준 거리는 바뀌지 않는다.

니콜라가 어떤 발판에 도착할 때마다 그 발판의 통행료를 낸다. 시작할 때 이미 서 있는 1번 발판의 통행료는 내지 않지만, 나중에 1번 발판으로 돌아오면 그때는 통행료를 내야 한다.

N번 발판에 도착할 때까지 내야 하는 통행료 합의 최솟값을 구하라.

첫째 줄에 발판의 개수 N이 주어진다. (2 <= N <= 1000)

다음 N개의 줄에는 1번 발판부터 N번 발판까지의 통행료가 차례대로 하나씩 주어진다. 각 통행료는 1 이상 500 이하의 정수이다.

N번 발판에 도착할 때까지 내야 하는 통행료 합의 최솟값을 출력한다.