문제
$N$ 개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다.
돌들을 왼쪽부터 1번 돌, 2번 돌,$\cdots,ドル $N$번 돌이라 하자. $i$번째 돌의 무게는 $A_i$이다.
당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 총 $N$번 반복하려고 한다.
돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.
가장 많은 점수를 얻을 수 있도록 돌을 가져가는 방법을 구하여라.
출력
첫째 줄에 최적의 방법으로 돌을 가져갔을 때 얻을 수 있는 점수를 출력한다.
노트
처음 위치 기준 왼쪽에서 5,ドル\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 3ドル$번째 돌과 5ドル$번째 돌을 가져갈 때 점수를 얻어 13ドル$점이 된다.
W3sicHJvYmxlbV9pZCI6IjIyMzU0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2NjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+JE4kIFx1YWMxY1x1Yzc1OCBcdWIzY2NcdWM3NzQgXHVjNzdjXHViODJjXHViODVjIFx1YjA5OFx1YzVmNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWIzY2NcdWM3NDAgXHVkNzcwXHVjMGM5IFx1YjYxMFx1YjI5NCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViM2NjXHViNGU0XHVjNzQ0IFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCAxXHViYzg4IFx1YjNjYywgMlx1YmM4OCBcdWIzY2MsJFxcY2RvdHMkLCAkTiRcdWJjODggXHViM2NjXHVjNzc0XHViNzdjIFx1ZDU1OFx1Yzc5MC4gJGkkXHViYzg4XHVjOWY4IFx1YjNjY1x1Yzc1OCBcdWJiMzRcdWFjOGNcdWIyOTQgJEFfaSRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBcdWIwOThcdWM1ZjRcdWI0MWMgXHViM2NjXHViNGU0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NDQgXHViYWE4XHViNGUwIFx1YjNjY1x1Yzc3NCBcdWM1YzZcdWM1YjRcdWM5YzggXHViNTRjXHVhZTRjXHVjOWMwIFx1Y2QxZCAkTiRcdWJjODggXHViYzE4XHViY2Y1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2NjXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwOCBcdWI1NGMsIFx1YjljY1x1YzU3ZCBcdWFkZjggXHViM2NjXHVjNzc0IFx1ZDYwNFx1YzdhYyBcdWIwOThcdWM1ZjRcdWI0MWMgXHViM2NjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzQgXHVjNTQ0XHViMmM4XHViYTcwLCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2NjXHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViM2NjIFx1YmFhOFx1YjQ1MCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2NjXHVhY2ZjIFx1YjJlNFx1Yjk3OCBcdWMwYzlcdWM3NzggXHVhY2JkXHVjNmIwIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFjMDBcdWM4MzhcdWFjMDQgXHViM2NjXHVjNzU4IFx1YmIzNFx1YWM4Y1x1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWIzY2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzAwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxIFxcbGUgTiBcXGxlIDMgXFx0aW1lcyAxMF41JCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCA8Y29kZT5CPFwvY29kZT4gXHViNjEwXHViMjk0IDxjb2RlPlc8XC9jb2RlPlx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0ICROJFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFMkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JFMkXHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTAgJFNfaSRcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjICRpJFx1YmM4OFx1YzlmOCBcdWIzY2NcdWM3NTggXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gPGNvZGU+QjxcL2NvZGU+XHViMjk0IFx1YjNjY1x1Yzc3NCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3ODRcdWM3NDQsIDxjb2RlPlc8XC9jb2RlPlx1YjI5NCBcdWIzY2NcdWM3NzQgXHVkNzcwXHVjMGM5XHVjNzg0XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMSBcXGxlIEFfaSBcXGxlIDEwXjkkKTxcL3A+XHJcblxyXG48cD4kQV9pJCBcdWIyOTQgJGkkXHViYzg4IFx1YjNjY1x1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzE0XHVjNzQ0IFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjOThcdWM3NGMgXHVjNzA0XHVjZTU4IFx1YWUzMFx1YzkwMCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgJDUsXFwgNixcXCAyLFxcIDMsXFwgNCxcXCA3LFxcIDgsXFwgMSRcdWJjODhcdWM5ZjggXHViM2NjXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQgJDMkXHViYzg4XHVjOWY4IFx1YjNjY1x1YWNmYyAkNSRcdWJjODhcdWM5ZjggXHViM2NjXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwOCBcdWI1NGMgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YzViNCAkMTMkXHVjODEwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIyMzU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RvbmVzIDEiLCJkZXNjcmlwdGlvbiI6IjxwPiROJCZuYnNwO3N0b25lcyBsYWJlbGVkIGZyb20mbmJzcDskMSQmbmJzcDt0byZuYnNwOyROJCZuYnNwO2FyZSBhcnJhbmdlZCBpbiBhIHJvdyBpbiBpbmNyZWFzaW5nIG9yZGVyLiBFYWNoIHN0b25lIGlzIGNvbG9yZWQgZWl0aGVyIHdoaXRlIG9yIGJsYWNrLiBUaGUgd2VpZ2h0IG9mIHRoZSZuYnNwOyRpJC10aCBzdG9uZSBpcyZuYnNwOyRBX2kkLjxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCByZW1vdmUgdGhlIHN0b25lcyBvbmUgYXQgYSB0aW1lIHVudGlsIGFsbCB0aGUgc3RvbmVzIGFyZSByZW1vdmVkLjxcL3A+XHJcblxyXG48cD5XaGVuIHJlbW92aW5nIGEgc3RvbmUsIGlmIHRoZSBzdG9uZSBpcyBub3QgdGhlIGxlZnRtb3N0IG9yIHJpZ2h0bW9zdCBvZiBhbGwgcmVtYWluaW5nIHN0b25lcywgYW5kIG5laXRoZXIgc3RvbmUgYWRqYWNlbnQgdG8gdGhlIHN0b25lIGJlaW5nIHJlbW92ZWQgbWF0Y2hlcyBpdCBpbiBjb2xvciwgeW91ciBzY29yZSBpbmNyZWFzZXMgYnkgdGhlIHdlaWdodCBvZiB0aGUgc3RvbmUgYmVpbmcgcmVtb3ZlZC4gVHdvIHN0b25lcyBhcmUgYWRqYWNlbnQgaWYgdGhlcmUgYXJlIG5vIHN0b25lcyBpbiBiZXR3ZWVuIHRob3NlIHR3by48XC9wPlxyXG5cclxuPHA+RmluZCBhIHdheSB0byByZW1vdmUgdGhlIHN0b25lcyB0byBtYXhpbWl6ZSB5b3VyIHNjb3JlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciZuYnNwOyROJCZuYnNwOygkMSBcXGxlIE4gXFxsZSAzMDBcXCwgMDAwJCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHN0cmluZyZuYnNwOyRTJCZuYnNwO29mIGxlbmd0aCZuYnNwOyROJCZuYnNwO3doZXJlIGVhY2ggY2hhcmFjdGVyIGlzIGVpdGhlciZuYnNwOzxjb2RlPkI8XC9jb2RlPiZuYnNwO29yJm5ic3A7PGNvZGU+VzxcL2NvZGU+LiBUaGUmbmJzcDskaSR0aCBjaGFyYWN0ZXIgb2YmbmJzcDskUyQsJm5ic3A7JFNfaSQsIGlzJm5ic3A7PGNvZGU+QjxcL2NvZGU+Jm5ic3A7aWYgdGhlJm5ic3A7JGkkLXRoIHN0b25lIGlzIGJsYWNrLCBvdGhlcndpc2UsJm5ic3A7JFNfaSQmbmJzcDtpcyZuYnNwOzxjb2RlPlc8XC9jb2RlPiZuYnNwO2FuZCB0aGUmbmJzcDskaSQtdGggc3RvbmUgaXMgd2hpdGUuPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zJm5ic3A7JE4kJm5ic3A7aW50ZWdlcnMmbmJzcDskQV8xLCBBXzIsIFxcY2RvdHMsIEFfTiQmbmJzcDsoJDEgXFxsZSBBX2kgXFxsZSAxMF45JCkuJm5ic3A7JEFfaSQmbmJzcDtyZXByZXNlbnRzIHRoZSB3ZWlnaHQgb2Ygc3RvbmUmbmJzcDskaSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIHNjb3JlIHRoYXQgY2FuIGJlIG9idGFpbmVkIGlmIHlvdSB0YWtlIHRoZSBzdG9uZXMgb3B0aW1hbGx5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=