시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjEwNDY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjJiXHVjNzkwXHViZjUxXHVhZTMwXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9waWNrZXQuanBnXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjQyMXB4OyBtYXJnaW4tbGVmdDoyMHB4OyB3aWR0aDo1MDBweFwiIFwvPlx1YzU0NFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWFjNzRcdWJjMThcdWM1NDVcdWFlMzBcdWI5N2MgXHViMmU0XHViOGU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMxOTBcdWFjMDBcdWI3N2QgXHVkNzk4XHVjNzQ0IFx1YWUzMFx1Yjk3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMTkwXHVhYzAwXHViNzdkIFx1YjA1ZFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjMjJiXHVjNzkwXHViOTdjIFx1YmY1MVx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOTkwXHVhZTM0XHViMmU0LiBcdWFkZjggXHVhYzhjXHVjNzg0XHVjNzU4IFx1YmMyOVx1YzJkZFx1Yzc0MCBcdWM3NzRcdWI4MDdcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1ZDYwNFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViNGU0XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1NDRcdWQ2MDRcdWM3NzRcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNjM5XHVjNzQwIFx1YjljOFx1YzljMFx1YjljOVx1YmM4OFx1YzlmOFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YzViNFx1YjVhNCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1ZDYwNFx1Yzc3NFx1YWMwMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjMGFjXHViNzdjXHVjOWMwXHVhY2UwIFx1YzU0NFx1ZDYwNFx1Yzc3NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWIyOTQgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM3NzRcdWM2YzNcdWQ1NWMgXHVjMjJiXHVjNzkwXHViNGU0XHVjNzU4IFx1ZDU2OVx1YzVkMCBcdWM3NThcdWQ1NzQgXHVjNjJjXHViNzdjXHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMCAxIDIgMyA0IDVcdWFjMDAgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNTQ0XHVkNjA0XHVjNzc0XHVhYzAwIDNcdWM3NDQgXHViZjUxXHVjNzNjXHViYTc0IFx1YzU0NFx1ZDYwNFx1Yzc3NFx1Yzc1OCBcdWM4MTBcdWMyMThcdWIyOTQgMiszKzQgPSA5IFx1YzgxMFx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgMSAyIDQgNVx1YWMwMCBcdWIwYThcdWM3NDAgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIDRcdWI5N2MgXHViZjUxXHViMjk0XHViMmU0XHViYTc0LCBcdWM1NDRcdWQ2MDRcdWM3NzRcdWM3NTggXHVjODEwXHVjMjE4XHViMjk0IDkrMis0KzUgPSAyMCBcdWM4MTBcdWM3NzQgXHViNDE4XHVhY2UwIFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMFx1YjI5NCAxIDIgNVx1YWMwMCBcdWIwYThcdWFjOGNcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwIDJcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOWNjIFx1YjBhOFx1YzU1OFx1Yzc0NCBcdWI1NGMgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMmJcdWM3OTAgXHViOWFjXHVjMmE0XHVkMmI4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzU0NFx1ZDYwNFx1Yzc3NFx1YWMwMCBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YzgxMFx1YzIxOFx1YjI5NCBcdWJhODdcdWM4MTBcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViOWNlXHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1Yzc4NVx1YjgyNSBcdWQ2MTVcdWMyZGRcdWM3NDAgPGVtPm4gazEgazIgLi4uIGtuIDxcL2VtPlx1Yzc3NFx1YmE3MCAsIDxlbT5uPFwvZW0+ICg8ZW0+bjxcL2VtPiAmbGU7IDIwMCkgXHVjNzQwIFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWMyMTggPGVtPmtpXHVjNzU4IFx1YmM5NFx1YzcwNFx1YjI5NDxcL2VtPiAxICZsZTsgPGVtPmtpPFwvZW0+ICZsZTsgMTAwIFx1YzY0MCBcdWFjMTlcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwXHVjMTFjIDxlbT5uPFwvZW0+ICZnZTsgMyBcdWM3NzRcdWJhNzAsIDxlbT5uPFwvZW0+PTAgXHVjNzdjIFx1YjU0YyBcdWM3ODVcdWI4MjVcdWM3NDQgXHViYzFiXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVhY2UwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaWNrIEl0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9waWNrZXQuanBnXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjQyMXB4OyB3aWR0aDo1MDBweFwiIFwvPllvdSBhcmUgcGxheWluZyBhIGdhbWUgb2YgUGljayBJdC4gWW91IGFyZSBnaXZlbiBhIGxpc3Qgb2YgcG9zaXRpdmUgaW50ZWdlcnMsIGFuZCB5b3UgYXJlIGFsbG93ZWQgdG8gc2VsZWN0IGFueSBudW1iZXIgb3RoZXIgdGhhbiB0aGUgZmlyc3Qgb3IgbGFzdCBudW1iZXIgaW4gdGhpcyBsaXN0LiBXaGVuIHlvdSBwaWNrIGEgbnVtYmVyLCB0aGF0IG51bWJlciBpcyByZW1vdmVkIGZyb20gdGhlIGJvYXJkLCBhbmQgeW91ciBzY29yZSBpbmNyZWFzZXMgYnkgdGhlIHN1bSBvZiB0aGUgbnVtYmVyIHRoYXQgeW91IHBpY2tlZCBhbmQgdGhlIHN1bSBvZiB0aGUgbmVpZ2hib3VyaW5nIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgbGlzdCBjb250YWluZWQgPHR0PjEgMiAzIDQgNTxcL3R0PiwgYW5kIHlvdSBwaWNrZWQgPHR0PjM8XC90dD4sIHlvdXIgc2NvcmUgd291bGQgYmUgPHR0PjIrMys0PTk8XC90dD4uIE9uIHRoZSBuZXh0IHR1cm4sIHlvdXIgbGlzdCB3b3VsZCBiZSA8dHQ+MSAyIDQgNTxcL3R0PiwgYW5kIGlmIHlvdSBwaWNrZWQgPHR0PjQ8XC90dD4gbmV4dCwgeW91ciBzY29yZSB3b3VsZCBiZSA8dHQ+OSsyKzQrNSA9IDIwPFwvdHQ+LCBsZWF2aW5nIHlvdSB3aXRoIHRoZSBsaXN0IDx0dD4xIDIgNTxcL3R0Pi4gVGhlIGdhbWUgY29uY2x1ZGVzIHdoZW4gdGhlcmUgYXJlIG9ubHkgdHdvIG51bWJlcnMgcmVtYWluaW5nLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGxpc3Qgb2YgbnVtYmVycywgd2hhdCBpcyB0aGUgbWF4aW11bSBzY29yZSB0aGF0IHlvdSBjYW4gb2J0YWluPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHdpbGwgY29uc2lzdCBvZiBhIG51bWJlciBvZiB0ZXN0IGNhc2VzIChhdCBtb3N0IDIwMCB0ZXN0IGNhc2VzKS4gQSB0ZXN0IGNhc2UgaXMgb2YgdGhlIGZvcm0gPGVtPm4gazxzdWI+MTxcL3N1Yj4gazxzdWI+MjxcL3N1Yj4gLi4uIGs8c3ViPm48XC9zdWI+PFwvZW0+IHdoZXJlIDxlbT5uPFwvZW0+ICg8ZW0+bjxcL2VtPiAmbGU7IDIwMCkgaXMgdGhlIG51bWJlciBvZiBudW1iZXJzIGluIHRoZSBsaXN0LCBhbmQgZWFjaCBpbnRlZ2VyIDxlbT5rPHN1Yj5pPFwvc3ViPjxcL2VtPiBzYXRpc2ZpZXMgMSAmbGU7IDxlbT5rPHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IDEwMCkuIEluIGFsbCB0ZXN0IGNhc2VzIDxlbT5uPFwvZW0+ICZnZTsgMywgZXhjZXB0IGluIHRoZSBjYXNlIHdoZXJlIDxlbT5uPFwvZW0+PTAsIHdoaWNoIGluZGljYXRlcyB0aGUgZW5kIG9mIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBtYXhpbXVtIHNjb3JlIGF0dGFpbmFibGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d