시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2172 851 594 44.763%

문제

근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.

예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이 때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.

입력

입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트케이스 마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적혀있는 수는 1이상 10,000이하다.

출력

각 테스트케이스마다 근우와 명우가 최선의 전략으로 임할 때 근우가 얻게되는 점수를 줄로 구분하여 출력한다.

예제 입력 1

2
4
1 2 5 2
9
1 1 1 1 2 2 2 2 2

예제 출력 1

6
8
W3sicHJvYmxlbV9pZCI6IjExMDYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZTc0XHViNGRjIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZGZjXHVjNmIwXHVjNjQwIFx1YmE4NVx1YzZiMFx1YjI5NCBcdWM3YWNcdWJiZjhcdWM3ODhcdWIyOTQgXHVjZTc0XHViNGRjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBOXHVhYzFjXHVjNzU4IFx1Y2U3NFx1YjRkY1x1YWMwMCBcdWM3N2NcdWI4MmNcdWI4NWMgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2U3NFx1YjRkY1x1YzVkMFx1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LiBcdWFkZmNcdWM2YjBcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWQxMzRcdWM3NzQgXHVjOWM0XHVkNTg5XHViNDE4XHViMjk0XHViMzcwIFx1ZDU1YyBcdWQxMzRcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTc0XHViNGRjXHViMDk4IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjZTc0XHViNGRjXHVhYzAwIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHViMGE4XHVjNTQ0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVkMTM0XHVjNzQwIFx1YmMxOFx1YmNmNVx1YjQxY1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhYzAwXHVjODM4XHVhYzA0IFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGZjXHVjNmIwXHVjNjQwIFx1YmE4NVx1YzZiMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzc0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNkNWNcdWMxMjBcdWM3NTggXHVjODA0XHViN2I1XHVjNzNjXHViODVjIFx1YWM4Y1x1Yzc4NFx1YzVkMCBcdWM3ODRcdWQ1NWNcdWIyZTQuIFx1YjE5M1x1YzVlY1x1Yzc4OFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjZmMgXHVjZTc0XHViNGRjXHVhYzAwIFx1YjE5M1x1YzVlY1x1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWFkZmNcdWM2YjBcdWFjMDAgXHVjNWJiXHViMjk0IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWNlNzRcdWI0ZGNcdWFjMDAgWzQsIDMsIDEsIDJdXHViODVjIFx1YjE5M1x1YzVlY1x1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmY1x1YzZiMFx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgNFx1YWMwMCBcdWM4MDFcdWQ3OGMgXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHViYTg1XHVjNmIwXHViMjk0IDNcdWM3NzQgXHVjODAxXHVkNzhjIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZmNcdWM2YjBcdWIyOTQgMlx1YWMwMCBcdWM4MDFcdWQ3OGMgXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHViYTg1XHVjNmIwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyAxXHVjNzc0IFx1YzgwMVx1ZDc4YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0LiBcdWM3NzQgXHViNTRjIFx1YWRmY1x1YzZiMFx1YzY0MCBcdWJhODVcdWM2YjBcdWIyOTQgXHVjZDVjXHVjMTIwXHVjNzU4IFx1YzgwNFx1YjdiNVx1YzczY1x1Yjg1YyBcdWM3ODRcdWQ1ODhcdWM3M2NcdWJhNzAsIFx1YWRmY1x1YzZiMFx1YWMwMCBcdWM1YmJcdWIyOTQgXHVjODEwXHVjMjE4XHViMjk0IDZcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBpXHViYzg4XHVjOWY4XHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIGlcdWJjODhcdWM5ZjhcdWM1ZDAgXHViMTkzXHVjNzc4IFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMThcdWIyOTQgMVx1Yzc3NFx1YzBjMSAxMCwwMDBcdWM3NzRcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWFkZmNcdWM2YjBcdWM2NDAgXHViYTg1XHVjNmIwXHVhYzAwIFx1Y2Q1Y1x1YzEyMFx1Yzc1OCBcdWM4MDRcdWI3YjVcdWM3M2NcdWI4NWMgXHVjNzg0XHVkNTYwIFx1YjU0YyBcdWFkZmNcdWM2YjBcdWFjMDAgXHVjNWJiXHVhYzhjXHViNDE4XHViMjk0IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTA2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhcmQgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2UgaXMgcGxheWluZyBhIHNpbXBsZSBidXQgaW50ZXJlc3RpbmcgY29tcHV0ZXIgZ2FtZSBvbiBoZXIgY29tcHV0ZXIuIFRoZSBnYW1lIHBsYXlzIGFzIGZvbGxvd3M6IHdoZW4gQWxpY2Ugc3RhcnRzIHRoZSBnYW1lLCB0aGUgY29tcHV0ZXIgc2hvd3MgbiBjYXJkcyBvbiB0aGUgbW9uaXRvciBpbiBhIGxpbmUuIEVhY2ggY2FyZCBpcyBhc3NvY2lhdGVkIHdpdGggYSBudW1iZXIgcHJpbnRlZCBvbiB0aGUgZmFjZSBhbmQgYWxsIHRoZSBjYXJkcyBhcmUgZmFjZWQgdXAgc28gdGhhdCBzaGUgY2FuIHNlZSBldmVyeSBudW1iZXIgcHJpbnRlZCBvbiB0aGUgY2FyZHMuIFNoZSBhbmQgdGhlIGNvbXB1dGVyIHJlcGVhdGVkbHkgcGljayB1cCBhIGNhcmQgaW4gdHVybiBlaXRoZXIgZnJvbSB0aGUgZnJvbnQgb3IgZnJvbSB0aGUgcmVhciBvZiB0aGUgbGluZSB1bnRpbCB0aGVyZSBpcyBubyBjYXJkIGluIHRoZSBsaW5lLiBTaGUgYWx3YXlzIHN0YXJ0cyB0aGUgZ2FtZS4gSW4gb3RoZXIgd29yZHMsIHNoZSBhbHdheXMgcGlja3MgdXAgYSBjYXJkIGZpcnN0LiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBmb3IgQWxpY2UgaXMgdG8gbWF4aW1pemUgdGhlIHN1bSBvZiBhbGwgdGhlIG51bWJlcnMgcHJpbnRlZCBvbiB0aGUgY2FyZHMgc2hlIHBpY2tzIHVwLiBTaGUgY29tcGxldGVseSB1bmRlcnN0YW5kcyBhIHN0cmF0ZWd5IHRvIG1ha2UgdGhlIHN1bSBtYXhpbWl6ZWQuIERlZmluaXRlbHkgdGhlIGNvbXB1dGVyIHdpbGwgcHJldmVudCBBbGljZSBmcm9tIG1ha2luZyBpdC48XC9wPlxyXG5cclxuPHA+SGVyZSBpcyBhbiBleGFtcGxlLiBUaGVyZSBhcmUgZm91ciBjYXJkcyBpbiBhIGxpbmUgYW5kIG51bWJlcnMgb24gdGhlIGNhcmRzIGFyZSAoNCwgMywgMSwgMikuIEFsaWNlIGZpcnN0IHBpY2tzIHVwIHRoZSBjYXJkIG9mIG51bWJlciA0IGZyb20gdGhlIGZyb250IG9mIHRoZSBsaW5lLiBUaGVuIHRoZSBjb21wdXRlciBwaWNrcyB1cCB0aGUgY2FyZCBvZiBudW1iZXIgMyBmcm9tIHRoZSBmcm9udC4gVGhlbiBBbGljZSBwaWNrcyB1cCB0aGUgY2FyZCBvZiBudW1iZXIgMiBmcm9tIHRoZSByZWFyLiBGaW5hbGx5LCB0aGUgY29tcHV0ZXIgcGlja3MgdXAgdGhlIGxhc3QgY2FyZCBvZiBudW1iZXIgMS4gVGhpcyBpcyB0aGUgYmVzdCBwaWNraW5nIG9yZGVyIGZvciBib3RoIEFsaWNlIGFuZCB0aGUgY29tcHV0ZXIsIGFuZCBBbGljZSBtYWtlcyB0aGUgc3VtIDYuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gbWFrZSBhIHByb2dyYW0gdGhhdCBjb21wdXRlcyB0aGUgc3VtIG9mIGFsbCB0aGUgbnVtYmVycyBvbiB0aGUgY2FyZHMgQWxpY2Ugc2VsZWN0cyBhbW9uZyBnaXZlbiBuIGNhcmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciwgbiAoMSAmbGU7IG4gJmxlOyAxLDAwMCksIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBjYXJkcy4gSW4gdGhlIGZvbGxvd2luZyBsaW5lLCBuIG51bWJlcnMgYXJlIGdpdmVuIGVhY2ggb2Ygd2hpY2ggZGVub3RlcyB0aGUgbnVtYmVyIHByaW50ZWQgb24gdGhlIGNhcmRzIGFuZCBpcyBzZXBhcmF0ZWQgYnkgYSBibGFuay4gRWFjaCBudW1iZXIgcHJpbnRlZCBvbiB0aGUgY2FyZHMgaXMgYmV0d2VlbiAxIGFuZCAxMCwwMDAsIGluY2x1c2l2ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYSBudW1iZXIgd2hpY2ggcmVwcmVzZW50cyB0aGUgc3VtIG9mIGFsbCB0aGUgbnVtYmVycyBwcmludGVkIG9uIHRoZSBjYXJkcyBBbGljZSBzZWxlY3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==