문제
NLCS Jeju에는 화재 경보가 울리면 모든 커플이 헤어진다는 징크스가 있다......
시이(swi)는 하라는 공부는 안 하고 연애만 하는 학생들이 NLCS Jeju에 너무 많은 것을 보고 이들에게 시이-빔을 쏘아 단죄하기로 하였다.
언제나처럼 화재경보기가 오작동해 학생 $N$명이 대피하여 운동장에 한 줄로 서있다. 시이는 커플인 두 사람 중 한 명 이상을 단죄하려고 한다. 하지만 이들 중 누가 커플인지 모르기 때문에 시이는 다음 규칙에 따라 학생들을 단죄하기로 하였다.
- 모든 서로 인접한 두 학생 중 한 명 이상을 단죄해야 한다.
하지만 각 학생은 시이-빔에 대한 저항력이 있어 앞에서 $i$번째 학생을 시이-빔으로 단죄하기 위해서는 $R_i$만큼의 에너지가 필요하다.
시이가 규칙을 만족하도록 학생들을 단죄하기 위해 필요한 총 에너지의 최솟값을 구하여라.
출력
시이가 규칙을 만족하도록 학생들을 단죄하기 위해 필요한 총 에너지의 최솟값을 정수로 출력한다.
제한
- 1ドル \le N \le 100,000円$
- 1ドル \le R_i \le 10^9$
두 번째, 네 번째 학생을 단죄하면 규칙을 만족한다.
W3sicHJvYmxlbV9pZCI6IjMxNjcwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI5XHViY2M0XHVkNTVjIFx1YjljOFx1YmM5NSBcdWFjZjVcdWFjYTkiLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cD5OTENTIEplanVcdWM1ZDBcdWIyOTQgXHVkNjU0XHVjN2FjIFx1YWNiZFx1YmNmNFx1YWMwMCBcdWM2YjhcdWI5YWNcdWJhNzQgXHViYWE4XHViNGUwIFx1Y2VlNFx1ZDUwY1x1Yzc3NCBcdWQ1ZTRcdWM1YjRcdWM5YzRcdWIyZTRcdWIyOTQgXHVjOWQ1XHVkMDZjXHVjMmE0XHVhYzAwIFx1Yzc4OFx1YjJlNC4uLi4uLjxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5cdWMyZGNcdWM3NzQoc3dpKVx1YjI5NCBcdWQ1NThcdWI3N2NcdWIyOTQgXHVhY2Y1XHViZDgwXHViMjk0IFx1YzU0OCBcdWQ1NThcdWFjZTAgXHVjNWYwXHVjNTYwXHViOWNjIFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgTkxDUyBKZWp1XHVjNWQwIFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1YmNmNFx1YWNlMCBcdWM3NzRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjMmRjXHVjNzc0LVx1YmU1NFx1Yzc0NCBcdWMzZDhcdWM1NDQgXHViMmU4XHVjOGM0XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI4XHVjODFjXHViMDk4XHVjYzk4XHViN2ZjIFx1ZDY1NFx1YzdhY1x1YWNiZFx1YmNmNFx1YWUzMFx1YWMwMCBcdWM2MjRcdWM3OTFcdWIzZDlcdWQ1NzQgXHVkNTU5XHVjMGRkICROJFx1YmE4NVx1Yzc3NCBcdWIzMDBcdWQ1M2NcdWQ1NThcdWM1ZWMgXHVjNmI0XHViM2Q5XHVjN2E1XHVjNWQwIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjMTFjXHVjNzg4XHViMmU0LiBcdWMyZGNcdWM3NzRcdWIyOTQgXHVjZWU0XHVkNTBjXHVjNzc4IFx1YjQ1MCBcdWMwYWNcdWI3OGMgXHVjOTExIFx1ZDU1YyBcdWJhODUgXHVjNzc0XHVjMGMxXHVjNzQ0IFx1YjJlOFx1YzhjNFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzRcdWI0ZTQgXHVjOTExIFx1YjIwNFx1YWMwMCBcdWNlZTRcdWQ1MGNcdWM3NzhcdWM5YzAgXHViYWE4XHViOTc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMyZGNcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YjJlOFx1YzhjNFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1ZDU1OVx1YzBkZCBcdWM5MTEgXHVkNTVjIFx1YmE4NSBcdWM3NzRcdWMwYzFcdWM3NDQgXHViMmU4XHVjOGM0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVhYzAxIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWMyZGNcdWM3NzQtXHViZTU0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MDBcdWQ1NmRcdWI4MjVcdWM3NzQgXHVjNzg4XHVjNWI0IFx1YzU1ZVx1YzVkMFx1YzExYyAkaSRcdWJjODhcdWM5ZjggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YzJkY1x1Yzc3NC1cdWJlNTRcdWM3M2NcdWI4NWMgXHViMmU4XHVjOGM0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCAkUl9pJFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM1ZDBcdWIxMDhcdWM5YzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWM3NzRcdWFjMDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViMmU4XHVjOGM0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDFkIFx1YzVkMFx1YjEwOFx1YzljMFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjODAwXHVkNTZkXHViODI1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRSXzEsUl8yLFxcY2RvdHMsUl9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMyZGNcdWM3NzRcdWFjMDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViMmU4XHVjOGM0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDFkIFx1YzVkMFx1YjEwOFx1YzljMFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjODE1XHVjMjE4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSBOIFxcbGUgMTAwXFwsMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlIFJfaSBcXGxlIDEwXjkkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHViNDUwIFx1YmM4OFx1YzlmOCwgXHViMTI0IFx1YmM4OFx1YzlmOCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHViMmU4XHVjOGM0XHVkNTU4XHViYTc0IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzE2NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFeGNlcHRpb25hbCBNYWdpYyBBdHRhY2siLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cD5UaGVyZSBpcyBhIHdlaXJkIGppbnggaW4gTkxDUyBKZWp1IHRoYXQgY291cGxlcyBicmVhayB1cCB3aGVuZXZlciB0aGVyZSBpcyBhIGZpcmUgYWxhcm0uPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlN3aSBkZWNpZGVkIHRvIHNob290IGEgU3dpLWJlYW0gdG8gcHVyZ2Ugc3R1ZGVudHMgd2hvIHdlcmUgZGF0aW5nIG90aGVyIHN0dWRlbnRzIGluc3RlYWQgb2Ygc3R1ZHlpbmcuPFwvcD5cclxuXHJcbjxwPkFzIGFsd2F5cywgYSBmYWxzZSBhbGFybSBoYXBwZW5lZDsgJE4kIHN0dWRlbnRzIGV2YWN1YXRlZCBhbmQgZm9ybWVkIGEgbGluZSBvbiB0aGUgYXN0cm90dXJmLiBTd2kgd2lsbCBwdXJnZSBhdCBsZWFzdCBvbmUgcGVyc29uIG91dCBvZiB0aGUgY291cGxlcy4gSG93ZXZlciwgc2luY2Ugc2hlIGRvZXMgbm90IGtub3cgd2hvIGhhcyBhIGJveWZyaWVuZFwvZ2lybGZyaWVuZCwgc2hlIGRlY2lkZWQgdG8gcHVyZ2Ugc3R1ZGVudHMgYmFzZWQgb24gdGhlIGZvbGxvd2luZyBjcml0ZXJpb24uPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U3dpIG5lZWRzIHRvIHB1cmdlIGF0IGxlYXN0IG9uZSBwZXJzb24gb3V0IG9mIGFsbCBwYWlycyBvZiBhZGphY2VudCBzdHVkZW50cy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Ib3dldmVyLCBlYWNoIHN0dWRlbnQgaGFzIGEgY2VydGFpbiBhbW91bnQgb2YgcmVzaXN0YW5jZSB0byB0aGUgU3dpLWJlYW0uIFRoZXJlZm9yZSwgc2hlIG5lZWRzICRSX2kkIG9mIGVuZXJneSB0byBwdXJnZSB0aGUgc3R1ZGVudCB3aG8gY29tZXMgJGkkLXRoIGZyb20gdGhlIGZyb250LjxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBtaW5pbXVtIGVuZXJneSByZXF1aXJlZCBmb3IgU3dpIHRvIHB1cmdlIHRoZSBzdHVkZW50cyBhY2NvcmRpbmcgdG8gdGhlIGNyaXRlcmlvbiBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXImbmJzcDskTiQgZGVub3RpbmcgdGhlIG51bWJlciBvZiBzdHVkZW50cy48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBpbnRlZ2VycyZuYnNwOyRSXzEsIFJfMiwgXFxjZG90cywgUl9OJCBkZW5vdGluZyB0aGUgc3R1ZGVudHMmIzM5OyZuYnNwO3Jlc2lzdGFuY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgYSBzaW5nbGUgaW50ZWdlciBkZW5vdGluZyB0aGUgbWluaW11bSBlbmVyZ3kgdGhhdCBTd2kgbmVlZHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAxMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgUl9pIFxcbGUgMTBeOSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5QdXJnaW5nIHNlY29uZCBhbmQgZm91cnRoIHN0dWRlbnQgd291bGQgYmUgb3B0aW1hbC48XC9wPlxyXG4ifV0=