시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 7 7 77.778%

문제

Nikola는 자신의 의지와는 상관없이 어떤 게임 속의 메인 캐릭터가 되어버렸다!이 게임은 1부터 N까지의 번호가 써진 일렬로 된 N개의 발판 위에서 진행된다.  Nikola는 1번 발판 위에서 시작하여 다른 발판 위로 점프하여 이동할 수 있다. 처음 이동할 때는 무조건 2번 발판 위로 움직이게 되어있으며, 이후의 이동에는 다음과 같은 제약이 따른다.

  • 양의 방향으로 이동할 경우 바로 전 단계보다 1칸 더 먼 거리로 점프해야 한다.
  • 음의 방향으로 이동할 경우 바로 전 단계에서 이동한 거리 만큼 점프할 수 있다.

예를 들어, 첫번째 점프 이후(2번째 발판 위에 있는 상황), Nikola는 4번 발판으로 뛰어 갈 수 있으며, 반대 방향인 1번 발판으로 뛰어 갈 수 있다.

그가 매번 각 발판 위에 도달 했을 때, 해당 구역의 통행료를 내야만 한다. Nikola는 가능하다면 N번 발판까지 이동하면서 지불해야하는 통행료를 최소로 만들고 싶어한다.

입력

첫째 줄에는 발판의 갯수 N이 2 ≤ N ≤ 1000 인 정수로 주어진다.

둘째 줄 부터 N+1번째 줄에는 1번 발판부터 N번 발판까지 순서대로 각 발판을 지나드는데 지불해야하는 통행료가 주어지며, 이들은 모두 500 이하의 양의 정수이다.

출력

Nikola가 N번째 발판에 도달하기 위한 통행료의 최소값을 첫번째 줄에 출력한다.

예제 입력

6
1
2
3
4
5
6

예제 출력

12

힌트