문제
NLCS Jeju에는 화재 경보가 울리면 모든 커플이 헤어진다는 징크스가 있다...
시이(swi)는 하라는 공부는 안하고 연애만 하는 학생들이 NLCS Jeju에 너무 많은 것을 보고 이들에게 시이-빔을 쏘아 단죄하기로 하였다.
언제나처럼 화재경보기가 오작동해 학생 $N$명이 대피하여 운동장에 한 줄로 서있다. 시이는 커플인 두 사람 중 한 명 이상을 단죄하려고 한다. 하지만 이들 중 누가 커플인지 모르기 때문에 시이는 다음 규칙에 따라 학생들을 단죄하기로 하였다.
- 모든 서로 인접한 두 학생 중 한 명 이상을 단죄해야 한다.
하지만 각 학생은 시이-빔에 대한 저항력이 있어 앞에서 $i$번째 학생을 시이-빔으로 단죄하기 위해서는 $R_i$만큼의 에너지가 필요하다.
이러한 시이의 행동에 분노한 학생들은 몇 명의 머리를 대머리로 만들어 시이-빔을 반사하려 한다. 대머리인 학생에게 시이-빔을 쏘면 대머리에 반사되어 시이가 공격을 입게 된다. 따라서 시이는 대머리가 아닌 학생에게만 시이-빔을 쏠 수 있다. 하지만 이웃한 두 학생을 모두 대머리로 만들면 미관상 단죄당하느니만 못하므로 이웃한 두 명의 학생을 모두 대머리로 만들 수 없다.
학생들은 일부 인원을 적절히 대머리로 만들어 시이가 단죄에 성공하기 위해 필요한 최소 에너지를 최대화하려고 한다. 학생들이 대머리가 되어 시이가 단죄하는 데 필요한 에너지가 최대일 때 얼마나 많은 에너지가 필요한지 구해 보자.
출력
학생들이 대머리가 되어 시이가 소모해야 하는 최소 에너지가 최대가 되었을 때 시이가 소모해야 하는 총 에너지를 정수로 출력한다.
제한
- 1ドル \le N \le 100,000円$
- 1ドル \le R_i \le 10^9$
- 학생들의 머리를 밀기 전에 대머리인 학생은 존재하지 않는다.
첫 번째, 네 번째 학생을 대머리로 만드는 것이 최적이다.
W3sicHJvYmxlbV9pZCI6IjMxNjc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI5XHViY2M0XHVkNTVjIFx1YmIzY1x1YjlhYyBcdWFjZjVcdWFjYTkiLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cD5OTENTIEplanVcdWM1ZDBcdWIyOTQgXHVkNjU0XHVjN2FjIFx1YWNiZFx1YmNmNFx1YWMwMCBcdWM2YjhcdWI5YWNcdWJhNzQgXHViYWE4XHViNGUwIFx1Y2VlNFx1ZDUwY1x1Yzc3NCBcdWQ1ZTRcdWM1YjRcdWM5YzRcdWIyZTRcdWIyOTQgXHVjOWQ1XHVkMDZjXHVjMmE0XHVhYzAwIFx1Yzc4OFx1YjJlNC4uLjxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5cdWMyZGNcdWM3NzQoc3dpKVx1YjI5NCBcdWQ1NThcdWI3N2NcdWIyOTQgXHVhY2Y1XHViZDgwXHViMjk0IFx1YzU0OFx1ZDU1OFx1YWNlMCBcdWM1ZjBcdWM1NjBcdWI5Y2MgXHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBOTENTIEplanVcdWM1ZDAgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc0MCBcdWFjODNcdWM3NDQgXHViY2Y0XHVhY2UwIFx1Yzc3NFx1YjRlNFx1YzVkMFx1YWM4YyBcdWMyZGNcdWM3NzQtXHViZTU0XHVjNzQ0IFx1YzNkOFx1YzU0NCBcdWIyZThcdWM4YzRcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjhcdWM4MWNcdWIwOThcdWNjOThcdWI3ZmMgXHVkNjU0XHVjN2FjXHVhY2JkXHViY2Y0XHVhZTMwXHVhYzAwIFx1YzYyNFx1Yzc5MVx1YjNkOVx1ZDU3NCBcdWQ1NTlcdWMwZGQgJE4kXHViYTg1XHVjNzc0IFx1YjMwMFx1ZDUzY1x1ZDU1OFx1YzVlYyBcdWM2YjRcdWIzZDlcdWM3YTVcdWM1ZDAgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMWNcdWM3ODhcdWIyZTQuIFx1YzJkY1x1Yzc3NFx1YjI5NCBcdWNlZTRcdWQ1MGNcdWM3NzggXHViNDUwIFx1YzBhY1x1Yjc4YyBcdWM5MTEgXHVkNTVjIFx1YmE4NSBcdWM3NzRcdWMwYzFcdWM3NDQgXHViMmU4XHVjOGM0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc3NFx1YjRlNCBcdWM5MTEgXHViMjA0XHVhYzAwIFx1Y2VlNFx1ZDUwY1x1Yzc3OFx1YzljMCBcdWJhYThcdWI5NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzJkY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViMmU4XHVjOGM0XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMTFjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVkNTU5XHVjMGRkIFx1YzkxMSBcdWQ1NWMgXHViYTg1IFx1Yzc3NFx1YzBjMVx1Yzc0NCBcdWIyZThcdWM4YzRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWFjMDEgXHVkNTU5XHVjMGRkXHVjNzQwIFx1YzJkY1x1Yzc3NC1cdWJlNTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgwMFx1ZDU2ZFx1YjgyNVx1Yzc3NCBcdWM3ODhcdWM1YjQgXHVjNTVlXHVjNWQwXHVjMTFjICRpJFx1YmM4OFx1YzlmOCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVjMmRjXHVjNzc0LVx1YmU1NFx1YzczY1x1Yjg1YyBcdWIyZThcdWM4YzRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0ICRSX2kkXHViOWNjXHVkMDdjXHVjNzU4IFx1YzVkMFx1YjEwOFx1YzljMFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMyZGNcdWM3NzRcdWM3NTggXHVkNTg5XHViM2Q5XHVjNWQwIFx1YmQ4NFx1YjE3OFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHViYTg3IFx1YmE4NVx1Yzc1OCBcdWJhMzhcdWI5YWNcdWI5N2MgXHViMzAwXHViYTM4XHViOWFjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNCBcdWMyZGNcdWM3NzQtXHViZTU0XHVjNzQ0IFx1YmMxOFx1YzBhY1x1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YjMwMFx1YmEzOFx1YjlhY1x1Yzc3OCBcdWQ1NTlcdWMwZGRcdWM1ZDBcdWFjOGMgXHVjMmRjXHVjNzc0LVx1YmU1NFx1Yzc0NCBcdWMzZDhcdWJhNzQgXHViMzAwXHViYTM4XHViOWFjXHVjNWQwIFx1YmMxOFx1YzBhY1x1YjQxOFx1YzViNCBcdWMyZGNcdWM3NzRcdWFjMDAgXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1Yzc4NVx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMyZGNcdWM3NzRcdWIyOTQgXHViMzAwXHViYTM4XHViOWFjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWQ1NTlcdWMwZGRcdWM1ZDBcdWFjOGNcdWI5Y2MgXHVjMmRjXHVjNzc0LVx1YmU1NFx1Yzc0NCBcdWMzZTAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc3NFx1YzZjM1x1ZDU1YyBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWIzMDBcdWJhMzhcdWI5YWNcdWI4NWMgXHViOWNjXHViNGU0XHViYTc0IFx1YmJmOFx1YWQwMFx1YzBjMSBcdWIyZThcdWM4YzRcdWIyZjlcdWQ1NThcdWIyOTBcdWIyYzhcdWI5Y2MgXHViYWJiXHVkNTU4XHViYmMwXHViODVjIFx1Yzc3NFx1YzZjM1x1ZDU1YyBcdWI0NTAgXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViMzAwXHViYTM4XHViOWFjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjNzdjXHViZDgwIFx1Yzc3OFx1YzZkMFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHViMzAwXHViYTM4XHViOWFjXHViODVjIFx1YjljY1x1YjRlNFx1YzViNCBcdWMyZGNcdWM3NzRcdWFjMDAgXHViMmU4XHVjOGM0XHVjNWQwIFx1YzEzMVx1YWNmNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM1ZDBcdWIxMDhcdWM5YzBcdWI5N2MgXHVjZDVjXHViMzAwXHVkNjU0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YjMwMFx1YmEzOFx1YjlhY1x1YWMwMCBcdWI0MThcdWM1YjQgXHVjMmRjXHVjNzc0XHVhYzAwIFx1YjJlOFx1YzhjNFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVkMFx1YjEwOFx1YzljMFx1YWMwMCBcdWNkNWNcdWIzMDBcdWM3N2MgXHViNTRjIFx1YzViY1x1YjljOFx1YjA5OCBcdWI5Y2VcdWM3NDAgXHVjNWQwXHViMTA4XHVjOWMwXHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1Y1x1YzljMCBcdWFkNmNcdWQ1NzQgXHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjODAwXHVkNTZkXHViODI1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJFJfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWIzMDBcdWJhMzhcdWI5YWNcdWFjMDAgXHViNDE4XHVjNWI0IFx1YzJkY1x1Yzc3NFx1YWMwMCBcdWMxOGNcdWJhYThcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM1ZDBcdWIxMDhcdWM5YzBcdWFjMDAgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YzVjOFx1Yzc0NCBcdWI1NGMgXHVjMmRjXHVjNzc0XHVhYzAwIFx1YzE4Y1x1YmFhOFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDFkIFx1YzVkMFx1YjEwOFx1YzljMFx1Yjk3YyBcdWM4MTVcdWMyMThcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAxMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgUl9pIFxcbGUgMTBeOSQ8XC9saT5cclxuXHQ8bGk+XHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YmEzOFx1YjlhY1x1Yjk3YyBcdWJjMDBcdWFlMzAgXHVjODA0XHVjNWQwIFx1YjMwMFx1YmEzOFx1YjlhY1x1Yzc3OCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4LCBcdWIxMjQgXHViYzg4XHVjOWY4IFx1ZDU1OVx1YzBkZFx1Yzc0NCBcdWIzMDBcdWJhMzhcdWI5YWNcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWNkNWNcdWM4MDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzE2NzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFeGNlcHRpb25hbCBQaHlzaWNhbCBBdHRhY2siLCJkZXNjcmlwdGlvbiI6IjxibG9ja3F1b3RlPlxyXG48cD5UaGVyZSBpcyBhIHdlaXJkIGppbnggaW4gTkxDUyBKZWp1IHRoYXQgY291cGxlcyBicmVhayB1cCB3aGVuZXZlciB0aGVyZSBpcyBhIGZpcmUgYWxhcm0uPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlN3aSBkZWNpZGVkIHRvIHNob290IGEgU3dpLWJlYW0gdG8gcHVyZ2Ugc3R1ZGVudHMgd2hvIHdlcmUgZGF0aW5nIG90aGVyIHN0dWRlbnRzIGluc3RlYWQgb2Ygc3R1ZHlpbmcuPFwvcD5cclxuXHJcbjxwPkFzIGFsd2F5cywgYSBmYWxzZSBhbGFybSBoYXBwZW5lZC4gVGh1cywgJE4kIHN0dWRlbnRzIGV2YWN1YXRlZCBhbmQgZm9ybWVkIGEgbGluZSBvbiB0aGUgYXN0cm90dXJmLiBTd2kgd2lsbCBwdXJnZSBhdCBsZWFzdCBvbmUgcGVyc29uIG91dCBvZiBlYWNoIGNvdXBsZS4gSG93ZXZlciwgc2luY2Ugc2hlIGRvZXMgbm90IGtub3cgd2hvIGhhcyBhIGJveWZyaWVuZFwvZ2lybGZyaWVuZCwgc2hlIGRlY2lkZWQgdG8gcHVyZ2Ugc3R1ZGVudHMgYmFzZWQgb24gdGhlIGZvbGxvd2luZyBjcml0ZXJpb24uPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U3dpIG5lZWRzIHRvIHB1cmdlIGF0IGxlYXN0IG9uZSBwZXJzb24gb3V0IG9mIGFsbCBwYWlycyBvZiBhZGphY2VudCBzdHVkZW50cy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Ib3dldmVyLCBlYWNoIHN0dWRlbnQgaGFzIGEgY2VydGFpbiBhbW91bnQgb2YgcmVzaXN0YW5jZSB0byB0aGUgU3dpLWJlYW0uIFRoZXJlZm9yZSwgc2hlIG5lZWRzICRSX2kkIG9mIGVuZXJneSB0byBwdXJnZSB0aGUgc3R1ZGVudCB3aG8gY29tZXMgJGkkLXRoIGZyb20gdGhlIGZyb250LjxcL3A+XHJcblxyXG48cD5TdHVkZW50cywgYW5ub3llZCBieSBTd2ksIHdpbGwgcmVmbGVjdCBTd2ktYmVhbSBieSBzaGF2aW5nIHNvbWUgb2YgdGhlIHN0dWRlbnRzJiMzOTsgaGFpci4gU2luY2UgYmFsZCBzdHVkZW50cyB3aWxsIHJlZmxlY3QgU3dpLWJlYW1zLCBTd2kgY2Fubm90IHNob290IFN3aS1iZWFtcyB0byB0aGVtLiBIb3dldmVyLCBtYWtpbmcgdHdvIGFkamFjZW50IHN0dWRlbnRzIGJhbGQgaXMgZXZlbiB3b3JzZSB0aGFuIHB1cmdpbmcgdGhlbSBkdWUgdG8gYWVzdGhldGljIHJlYXNvbnMsIHNvIHN0dWRlbnRzIGNhbm5vdCBzaGF2ZSBib3RoIG9mIHR3byBhZGphY2VudCBzdHVkZW50cyYjMzk7IGhhaXIuPFwvcD5cclxuXHJcbjxwPlN0dWRlbnRzIHdpbGwgYXBwcm9wcmlhdGVseSBzaGF2ZSBzb21lIHN0dWRlbnRzJiMzOTsgaGFpciB0byBtYXhpbWlzZSB0aGUgYW1vdW50IG9mIGVuZXJneSBTd2kgbmVlZHMgdG8gc3VjY2Vzc2Z1bGx5IHB1cmdlIGNvdXBsZXMuIEZpbmQgdGhlIGVuZXJneSByZXF1aXJlZCBmb3IgU3dpIHRvIHB1cmdlIHRoZSBzdHVkZW50cyB3aGVuIHRoZSBlbmVyZ3kgcmVxdWlyZWQgdG8gZG8gc28gaXMgbWF4aW11bSBkdWUgdG8gc3R1ZGVudHMgc2hhdmluZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXImbmJzcDskTiQgJC0kIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgaW50ZWdlcnMgJFJfaSQgJC0kIHRoZSAkaSQtdGgmbmJzcDtzdHVkZW50JiMzOTtzJm5ic3A7cmVzaXN0YW5jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBhIHNpbmdsZSBpbnRlZ2VyJm5ic3A7JC0kIHRoZSZuYnNwO3RvdGFsIGVuZXJneSB0aGF0IFN3aSB3aWxsIG5lZWQmbmJzcDt3aGVuIHRoZSBzdHVkZW50cyBzaGF2ZSB0aGVpciBoZWFkcyBhbmQgdGhlIG1pbmltdW0gZW5lcmd5IHRoYXQgU3dpIG5lZWRzIGlzIGF0IHRoZSZuYnNwO21heGltdW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAxMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgUl9pIFxcbGUgMTBeOSQ8XC9saT5cclxuXHQ8bGk+Tm8gc3R1ZGVudCBpcyBiYWxkIGJlZm9yZSBzaGF2aW5nIHRoZWlyIGhlYWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+SXQgaXMgb3B0aW1hbCB0byBiYWxkIHRoZSBmaXJzdCBhbmQgZm91cnRoIHN0dWRlbnQuPFwvcD5cclxuIn1d