시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 57 17 12 34.286%

문제

아현이는 건반악기를 다루기 때문에 손가락 힘을 기르기 위해 손가락 끝을 이용해 숫자를 뽑는 게임을 즐긴다. 그 게임의 방식은 이렇다.

아현이에게 양의 정수들의 리스트가 주어진다. 그리고 아현이는 리스트의 첫번째 혹은 마지막번째의 숫자를 제외한 어떤 숫자를 선택할 수 있다. 아현이가 숫자를 선택했을 때, 그 숫자는 리스트에서 사라지고 아현이의 점수는 선택한 숫자와 이웃한 숫자들의 합에 의해 올라간다.

예를 들면 리스트에 1 2 3 4 5가 있다고 하자. 아현이가 3을 뽑으면 아현이의 점수는 2+3+4 = 9 점이 된다. 그 다음 1 2 4 5가 남은 상태에서 4를 뽑는다면, 아현이의 점수는 9+2+4+5 = 20 점이 되고 리스트에는 1 2 5가 남게된다. 이 게임은 리스트에 2개의 숫자만 남았을 때 끝난다.

숫자 리스트가 주어졌을 때, 아현이가 받을 수 있는 가장 높은 점수는 몇점일까?

입력

입력은 많은 테스트케이스로 구성된다. 입력 형식은 n k1 k2 ... kn 이며 , n (n ≤ 200) 은 리스트의 숫자의 개수이고 각각의 정수 ki의 범위는 1 ≤ ki ≤ 100 와 같다. 모든 테스트 케이스에서 n ≥ 3 이며, n=0 일 때 입력을 받는 것을 종료한다.

출력

각각의 케이스에 따라 받을 수 있는 최고 점수를 출력한다.

예제 입력 1

5 1 2 3 4 5
5 2 1 5 3 4
6 30 20 40 50 70 60
0

예제 출력 1

30
31
570
W3sicHJvYmxlbV9pZCI6IjEwNDY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjJiXHVjNzkwXHViZjUxXHVhZTMwXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9waWNrZXQuanBnXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjQyMXB4OyBtYXJnaW4tbGVmdDoyMHB4OyB3aWR0aDo1MDBweFwiIFwvPlx1YzU0NFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWFjNzRcdWJjMThcdWM1NDVcdWFlMzBcdWI5N2MgXHViMmU0XHViOGU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMxOTBcdWFjMDBcdWI3N2QgXHVkNzk4XHVjNzQ0IFx1YWUzMFx1Yjk3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMTkwXHVhYzAwXHViNzdkIFx1YjA1ZFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjMjJiXHVjNzkwXHViOTdjIFx1YmY1MVx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOTkwXHVhZTM0XHViMmU0LiBcdWFkZjggXHVhYzhjXHVjNzg0XHVjNzU4IFx1YmMyOVx1YzJkZFx1Yzc0MCBcdWM3NzRcdWI4MDdcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1ZDYwNFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViNGU0XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1NDRcdWQ2MDRcdWM3NzRcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWQ2MzlcdWM3NDAgXHViOWM4XHVjOWMwXHViOWM5XHViYzg4XHVjOWY4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgXHVjNWI0XHViNWE0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHVkNjA0XHVjNzc0XHVhYzAwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMFx1YzExYyBcdWMwYWNcdWI3N2NcdWM5YzBcdWFjZTAgXHVjNTQ0XHVkNjA0XHVjNzc0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNjQwIFx1Yzc3NFx1YzZjM1x1ZDU1YyBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWM2MmNcdWI3N2NcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwIDEgMiAzIDQgNVx1YWMwMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM1NDRcdWQ2MDRcdWM3NzRcdWFjMDAgM1x1Yzc0NCBcdWJmNTFcdWM3M2NcdWJhNzQgXHVjNTQ0XHVkNjA0XHVjNzc0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCAyKzMrNCA9IDkgXHVjODEwXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyAxIDIgNCA1XHVhYzAwIFx1YjBhOFx1Yzc0MCBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMgNFx1Yjk3YyBcdWJmNTFcdWIyOTRcdWIyZTRcdWJhNzQsIFx1YzU0NFx1ZDYwNFx1Yzc3NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWIyOTQgOSsyKzQrNSA9IDIwIFx1YzgxMFx1Yzc3NCBcdWI0MThcdWFjZTAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwXHViMjk0IDEgMiA1XHVhYzAwIFx1YjBhOFx1YWM4Y1x1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgMlx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5Y2MgXHViMGE4XHVjNTU4XHVjNzQ0IFx1YjU0YyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIyYlx1Yzc5MCBcdWI5YWNcdWMyYTRcdWQyYjhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNTQ0XHVkNjA0XHVjNzc0XHVhYzAwIFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjODEwXHVjMjE4XHViMjk0IFx1YmE4N1x1YzgxMFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI5Y2VcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVjNzg1XHViODI1IFx1ZDYxNVx1YzJkZFx1Yzc0MCA8ZW0+biBrMSBrMiAuLi4ga24gPFwvZW0+XHVjNzc0XHViYTcwICwgPGVtPm48XC9lbT4gKDxlbT5uPFwvZW0+ICZsZTsgMjAwKSBcdWM3NDAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzgxNVx1YzIxOCA8ZW0+a2lcdWM3NTggXHViYzk0XHVjNzA0XHViMjk0PFwvZW0+IDEgJmxlOyA8ZW0+a2k8XC9lbT4gJmxlOyAxMDAgXHVjNjQwIFx1YWMxOVx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgPGVtPm48XC9lbT4gJmdlOyAzIFx1Yzc3NFx1YmE3MCwgPGVtPm48XC9lbT49MCBcdWM3N2MgXHViNTRjIFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWJjMWJcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWFjZTAgXHVjODEwXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQ2OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpY2sgSXQiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL3BpY2tldC5qcGdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6NDIxcHg7IHdpZHRoOjUwMHB4XCIgXC8+WW91IGFyZSBwbGF5aW5nIGEgZ2FtZSBvZiBQaWNrIEl0LiBZb3UgYXJlIGdpdmVuIGEgbGlzdCBvZiBwb3NpdGl2ZSBpbnRlZ2VycywgYW5kIHlvdSBhcmUgYWxsb3dlZCB0byBzZWxlY3QgYW55IG51bWJlciBvdGhlciB0aGFuIHRoZSBmaXJzdCBvciBsYXN0IG51bWJlciBpbiB0aGlzIGxpc3QuIFdoZW4geW91IHBpY2sgYSBudW1iZXIsIHRoYXQgbnVtYmVyIGlzIHJlbW92ZWQgZnJvbSB0aGUgYm9hcmQsIGFuZCB5b3VyIHNjb3JlIGluY3JlYXNlcyBieSB0aGUgc3VtIG9mIHRoZSBudW1iZXIgdGhhdCB5b3UgcGlja2VkIGFuZCB0aGUgc3VtIG9mIHRoZSBuZWlnaGJvdXJpbmcgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHRoZSBsaXN0IGNvbnRhaW5lZCA8dHQ+MSAyIDMgNCA1PFwvdHQ+LCBhbmQgeW91IHBpY2tlZCA8dHQ+MzxcL3R0PiwgeW91ciBzY29yZSB3b3VsZCBiZSA8dHQ+MiszKzQ9OTxcL3R0Pi4gT24gdGhlIG5leHQgdHVybiwgeW91ciBsaXN0IHdvdWxkIGJlIDx0dD4xIDIgNCA1PFwvdHQ+LCBhbmQgaWYgeW91IHBpY2tlZCA8dHQ+NDxcL3R0PiBuZXh0LCB5b3VyIHNjb3JlIHdvdWxkIGJlIDx0dD45KzIrNCs1ID0gMjA8XC90dD4sIGxlYXZpbmcgeW91IHdpdGggdGhlIGxpc3QgPHR0PjEgMiA1PFwvdHQ+LiBUaGUgZ2FtZSBjb25jbHVkZXMgd2hlbiB0aGVyZSBhcmUgb25seSB0d28gbnVtYmVycyByZW1haW5pbmcuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbGlzdCBvZiBudW1iZXJzLCB3aGF0IGlzIHRoZSBtYXhpbXVtIHNjb3JlIHRoYXQgeW91IGNhbiBvYnRhaW4/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgd2lsbCBjb25zaXN0IG9mIGEgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKGF0IG1vc3QgMjAwIHRlc3QgY2FzZXMpLiBBIHRlc3QgY2FzZSBpcyBvZiB0aGUgZm9ybSA8ZW0+biBrPHN1Yj4xPFwvc3ViPiBrPHN1Yj4yPFwvc3ViPiAuLi4gazxzdWI+bjxcL3N1Yj48XC9lbT4gd2hlcmUgPGVtPm48XC9lbT4gKDxlbT5uPFwvZW0+ICZsZTsgMjAwKSBpcyB0aGUgbnVtYmVyIG9mIG51bWJlcnMgaW4gdGhlIGxpc3QsIGFuZCBlYWNoIGludGVnZXIgPGVtPms8c3ViPmk8XC9zdWI+PFwvZW0+IHNhdGlzZmllcyAxICZsZTsgPGVtPms8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgMTAwKS4gSW4gYWxsIHRlc3QgY2FzZXMgPGVtPm48XC9lbT4gJmdlOyAzLCBleGNlcHQgaW4gdGhlIGNhc2Ugd2hlcmUgPGVtPm48XC9lbT49MCwgd2hpY2ggaW5kaWNhdGVzIHRoZSBlbmQgb2YgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIG1heGltdW0gc2NvcmUgYXR0YWluYWJsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=