시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 13 13 56.522%

문제

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번째 발판에 도달하기 위한 통행료의 최소값을 첫번째 줄에 출력한다.

예제 입력 1

6
1
2
3
4
5
6

예제 출력 1

12

힌트

W3sicHJvYmxlbV9pZCI6IjI5NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOSUtPTEEiLCJkZXNjcmlwdGlvbiI6IjxwPk5pa29sYVx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzU4XHVjOWMwXHVjNjQwXHViMjk0IFx1YzBjMVx1YWQwMFx1YzVjNlx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVhYzhjXHVjNzg0IFx1YzE4ZFx1Yzc1OCBcdWJhNTRcdWM3NzggXHVjZTkwXHViOWFkXHVkMTMwXHVhYzAwIFx1YjQxOFx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNCFcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwJm5ic3A7MVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWMzNjhcdWM5YzQmbmJzcDtcdWM3N2NcdWI4MmNcdWI4NWMgXHViNDFjJm5ic3A7Tlx1YWMxY1x1Yzc1OCBcdWJjMWNcdWQzMTAmbmJzcDtcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LiAmbmJzcDtOaWtvbGFcdWIyOTQgMVx1YmM4OCBcdWJjMWNcdWQzMTAmbmJzcDtcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1YjJlNFx1Yjk3OCBcdWJjMWNcdWQzMTAmbmJzcDtcdWM3MDRcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTU4XHVjNWVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNjOThcdWM3NGMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0Y1x1YjI5NCBcdWJiMzRcdWM4NzBcdWFjNzQgMlx1YmM4OCBcdWJjMWNcdWQzMTAmbmJzcDtcdWM3MDRcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHVhYzhjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzc0XHVkNmM0XHVjNzU4IFx1Yzc3NFx1YjNkOVx1YzVkMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzgxY1x1YzU3ZFx1Yzc3NCBcdWI1MzBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNTkxXHVjNzU4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YmMxNFx1Yjg1YyBcdWM4MDQgXHViMmU4XHVhY2M0XHViY2Y0XHViMmU0IDFcdWNlNzggXHViMzU0IFx1YmEzYyBcdWFjNzBcdWI5YWNcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzRjXHVjNzU4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YmMxNFx1Yjg1YyBcdWM4MDQgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWFjNzBcdWI5YWMgXHViOWNjXHVkMDdjIFx1YzgxMFx1ZDUwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM4MTBcdWQ1MDQgXHVjNzc0XHVkNmM0KDJcdWJjODhcdWM5ZjggXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQ2NjkpLCBOaWtvbGFcdWIyOTQgNFx1YmM4OCBcdWJjMWNcdWQzMTBcdWM3M2NcdWI4NWMgXHViNmYwXHVjNWI0IFx1YWMwOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzc4IDFcdWJjODggXHViYzFjXHVkMzEwXHVjNzNjXHViODVjIFx1YjZmMFx1YzViNCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHVhYzAwIFx1YjllNFx1YmM4OCBcdWFjMDEgXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHVjNWQwIFx1YjNjNFx1YjJlYyBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWQ1NzRcdWIyZjkgXHVhZDZjXHVjNWVkXHVjNzU4Jm5ic3A7XHVkMWI1XHVkNTg5XHViOGNjXHViOTdjIFx1YjBiNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuIE5pa29sYVx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgTlx1YmM4OCBcdWJjMWNcdWQzMTBcdWFlNGNcdWM5YzAgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0XHVjMTFjIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1YjljY1x1YjRlNFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxY1x1ZDMxMFx1Yzc1OCBcdWFjMmZcdWMyMTggTlx1Yzc3NCZuYnNwOzIgJmxlOyBOICZsZTsgMTAwMCBcdWM3NzggXHVjODE1XHVjMjE4XHViODVjJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0IFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDFcdWJjODggXHViYzFjXHVkMzEwXHViZDgwXHVkMTMwIE5cdWJjODggXHViYzFjXHVkMzEwXHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyZuYnNwO1x1YWMwMSBcdWJjMWNcdWQzMTBcdWM3NDQgXHVjOWMwXHViMDk4XHViNGRjXHViMjk0XHViMzcwIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIDUwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OaWtvbGFcdWFjMDAgTlx1YmM4OFx1YzlmOCBcdWJjMWNcdWQzMTBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOSUtPTEEiLCJkZXNjcmlwdGlvbiI6IjxwPkFnYWluc3QgaGlzIG93biB3aWxsLCBOaWtvbGEgaGFzIGJlY29tZSB0aGUgbWFpbiBjaGFyYWN0ZXIgaW4gYSBnYW1lLiBUaGUgZ2FtZSBpcyBwbGF5ZWQgb24gYSByb3cgb2YgTiBzcXVhcmVzLCBudW1iZXJlZCAxIHRvIE4uIE5pa29sYSBpcyBpbml0aWFsbHkgaW4gc3F1YXJlIDEgYW5kIGNhbiBqdW1wIHRvIG90aGVyIHNxdWFyZXMuIE5pa29sYSYjMzk7cyBmaXJzdCBqdW1wIG11c3QgYmUgdG8gc3F1YXJlIDIuIEVhY2ggc3Vic2VxdWVudCBqdW1wIG11c3Qgc2F0aXNmeSB0d28gY29uc3RyYWludHM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SWYgdGhlIGp1bXAgaXMgaW4gdGhlIGZvcndhcmQgZGlyZWN0aW9uLCBpdCBtdXN0IGJlIG9uZSBzcXVhcmUgbG9uZ2VyIHRoYW4gdGhlIHByZWNlZGluZyBqdW1wLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiB0aGUganVtcCBpcyBpbiB0aGUgYmFja3dhcmQgZGlyZWN0aW9uLCBpdCBtdXN0IGJlIGV4YWN0bHkgdGhlIHNhbWUgbGVuZ3RoIGFzIHRoZSBwcmVjZWRpbmcganVtcC4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgYWZ0ZXIgdGhlIGZpcnN0IGp1bXAgKHdoZW4gb24gc3F1YXJlIDIpLCBOaWtvbGEgY2FuIGp1bXAgYmFjayB0byBzcXVhcmUgMSBvciBmb3J3YXJkcyB0byBzcXVhcmUgNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgdGltZSBoZSBlbnRlcnMgYSBzcXVhcmUsIE5pa29sYSBtdXN0IHBheSBhbiBlbnRyeSBmZWUuIE5pa29sYSYjMzk7cyBnb2FsIGlzIHRvIGdldCBmcm9tIHNxdWFyZSAxIHRvIHNxdWFyZSBOIGFzIGNoZWFwbHkgYXMgcG9zc2libGUuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIHNtYWxsZXN0IHRvdGFsIGNvc3QgZm9yIE5pa29sYSB0byBnZXQgdG8gc3F1YXJlIE4uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOLCAyICZsZTsgTiAmbGU7IDEwMDAsIHRoZSBudW1iZXIgb2Ygc3F1YXJlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhlIGVudHJ5IGZlZSBmb3Igb25lIHNxdWFyZSwgYSBwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiA1MDAuIFRoZSBlbnRyeSBmZWVzIHdpbGwgYmUgZ2l2ZW4gaW4gb3JkZXIgZm9yIHNxdWFyZXMgMSB0byBOLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgdG90YWwgY29zdCBmb3IgTmlrb2xhIHRvIGdldCB0byBzcXVhcmUgTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d