숫자가 쓰여진 징검다리를 건너는 경우 밟은 징검다리의 숫자 만큼의 돈을 지불하는 경우 최소의 돈으로 건너는 방법을 구하는 문제이다. (단 ,2 칸 까지 점프 할 수 있다고 하자.)

• 징검다리가 2 개 있다면 징검다리를 하나도 사용하지 않고 건널수 있으므로 지불할 돈이 없고

• 징검다리의수가 3 개이고 쓰여진 숫자가

  1 9 3

  이면, 첫 번째 징검다리를 밟고 지나간다면 1 원으로 건너는게 최소이다.

• 징검다리 수가 10 개 이고 쓰여진 숫자가 아래와 같다면

  3 2 8 2 4 9 1 2 3 4

  

  최소로 건널수 있는 비용은 2+2+1+2 = 7 이다.

입력 방법

출력 방법

입출력 예

입력

10
3 2 8 2 4 9 1 2 3 4

출력

7

★ 징검다리 동작보기(applet)