시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 39 16 16 42.105%

문제

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
W3sicHJvYmxlbV9pZCI6IjI5NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOSUtPTEEiLCJkZXNjcmlwdGlvbiI6IjxwPk5pa29sYVx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzU4XHVjOWMwXHVjNjQwXHViMjk0IFx1YzBjMVx1YWQwMFx1YzVjNlx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVhYzhjXHVjNzg0IFx1YzE4ZFx1Yzc1OCBcdWJhNTRcdWM3NzggXHVjZTkwXHViOWFkXHVkMTMwXHVhYzAwIFx1YjQxOFx1YzViNFx1YmM4NFx1YjgzOFx1YjJlNCEgXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCZuYnNwOzFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjNGYwXHVjNzc4Jm5ic3A7XHVjNzdjXHViODJjXHViODVjIFx1YjQxYyZuYnNwO05cdWFjMWNcdWM3NTggXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHVjNWQwXHVjMTFjIFx1YzljNFx1ZDU4OVx1YjQxY1x1YjJlNC4gJm5ic3A7Tmlrb2xhXHViMjk0IDFcdWJjODggXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWIyZTRcdWI5NzggXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHViODVjIFx1YzgxMFx1ZDUwNFx1ZDU1OFx1YzVlYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjYzk4XHVjNzRjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGNcdWIyOTQgXHViYjM0XHVjODcwXHVhYzc0IDJcdWJjODggXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWM4YyBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzRcdWQ2YzRcdWM3NTggXHVjNzc0XHViM2Q5XHVjNWQwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODFjXHVjNTdkXHVjNzc0IFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1OTFcdWM3NTggXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWFjYmRcdWM2YjAgXHViYzE0XHViODVjIFx1YzgwNCBcdWIyZThcdWFjYzRcdWJjZjRcdWIyZTQgMVx1Y2U3OCBcdWIzNTQgXHViYTNjIFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NGNcdWM3NTggXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWFjYmRcdWM2YjAgXHViYzE0XHViODVjIFx1YzgwNCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTVjIFx1YWM3MFx1YjlhYyBcdWI5Y2NcdWQwN2MgXHVjODEwXHVkNTA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTBcdWQ1MDQgXHVjNzc0XHVkNmM0KDJcdWJjODhcdWM5ZjggXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQ2NjkpLCBOaWtvbGFcdWIyOTQgNFx1YmM4OCBcdWJjMWNcdWQzMTBcdWM3M2NcdWI4NWMgXHViNmYwXHVjNWI0IFx1YWMwOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzc4IDFcdWJjODggXHViYzFjXHVkMzEwXHVjNzNjXHViODVjIFx1YjZmMFx1YzViNCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHVhYzAwIFx1YjllNFx1YmM4OCBcdWFjMDEgXHViYzFjXHVkMzEwJm5ic3A7XHVjNzA0XHVjNWQwIFx1YjNjNFx1YjJlYyBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWQ1NzRcdWIyZjkgXHVhZDZjXHVjNWVkXHVjNzU4Jm5ic3A7XHVkMWI1XHVkNTg5XHViOGNjXHViOTdjIFx1YjBiNFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuIE5pa29sYVx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgTlx1YmM4OCBcdWJjMWNcdWQzMTBcdWFlNGNcdWM5YzAgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0XHVjMTFjIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVkMWI1XHVkNTg5XHViOGNjXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMWNcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQmbmJzcDsyICZsZTsgTiAmbGU7IDEwMDAgXHVjNzc4IFx1YzgxNVx1YzIxOFx1Yjg1YyZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IDFcdWJjODggXHViYzFjXHVkMzEwXHViZDgwXHVkMTMwIE5cdWJjODggXHViYzFjXHVkMzEwXHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDEgXHViYzFjXHVkMzEwIFx1YzcwNFx1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NThcdWIyOTRcdWIzNzAgXHVjOWMwXHViZDg4XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIDUwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OaWtvbGFcdWFjMDAgTlx1YmM4OFx1YzlmOCBcdWJjMWNcdWQzMTBcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTklLT0xBIiwiZGVzY3JpcHRpb24iOiI8cD5BZ2FpbnN0IGhpcyBvd24gd2lsbCwgTmlrb2xhIGhhcyBiZWNvbWUgdGhlIG1haW4gY2hhcmFjdGVyIGluIGEgZ2FtZS4gVGhlIGdhbWUgaXMgcGxheWVkIG9uIGEgcm93IG9mIE4gc3F1YXJlcywgbnVtYmVyZWQgMSB0byBOLiBOaWtvbGEgaXMgaW5pdGlhbGx5IGluIHNxdWFyZSAxIGFuZCBjYW4ganVtcCB0byBvdGhlciBzcXVhcmVzLiBOaWtvbGEmIzM5O3MgZmlyc3QganVtcCBtdXN0IGJlIHRvIHNxdWFyZSAyLiBFYWNoIHN1YnNlcXVlbnQganVtcCBtdXN0IHNhdGlzZnkgdHdvIGNvbnN0cmFpbnRzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmIHRoZSBqdW1wIGlzIGluIHRoZSBmb3J3YXJkIGRpcmVjdGlvbiwgaXQgbXVzdCBiZSBvbmUgc3F1YXJlIGxvbmdlciB0aGFuIHRoZSBwcmVjZWRpbmcganVtcC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgdGhlIGp1bXAgaXMgaW4gdGhlIGJhY2t3YXJkIGRpcmVjdGlvbiwgaXQgbXVzdCBiZSBleGFjdGx5IHRoZSBzYW1lIGxlbmd0aCBhcyB0aGUgcHJlY2VkaW5nIGp1bXAuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGFmdGVyIHRoZSBmaXJzdCBqdW1wICh3aGVuIG9uIHNxdWFyZSAyKSwgTmlrb2xhIGNhbiBqdW1wIGJhY2sgdG8gc3F1YXJlIDEgb3IgZm9yd2FyZHMgdG8gc3F1YXJlIDQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IHRpbWUgaGUgZW50ZXJzIGEgc3F1YXJlLCBOaWtvbGEgbXVzdCBwYXkgYW4gZW50cnkgZmVlLiBOaWtvbGEmIzM5O3MgZ29hbCBpcyB0byBnZXQgZnJvbSBzcXVhcmUgMSB0byBzcXVhcmUgTiBhcyBjaGVhcGx5IGFzIHBvc3NpYmxlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBzbWFsbGVzdCB0b3RhbCBjb3N0IGZvciBOaWtvbGEgdG8gZ2V0IHRvIHNxdWFyZSBOLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiwgMiAmbGU7IE4gJmxlOyAxMDAwLCB0aGUgbnVtYmVyIG9mIHNxdWFyZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRoZSBlbnRyeSBmZWUgZm9yIG9uZSBzcXVhcmUsIGEgcG9zaXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gNTAwLiBUaGUgZW50cnkgZmVlcyB3aWxsIGJlIGdpdmVuIGluIG9yZGVyIGZvciBzcXVhcmVzIDEgdG8gTi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IHRvdGFsIGNvc3QgZm9yIE5pa29sYSB0byBnZXQgdG8gc3F1YXJlIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==