시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2658 1039 731 43.772%

문제

근우와 명우는 재미있는 카드 게임을 하고 있다. 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+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWNlNzRcdWI0ZGNcdWFjMDAgWzQsIDMsIDEsIDJdXHViODVjIFx1YjE5M1x1YzVlY1x1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmY1x1YzZiMFx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgNFx1YWMwMCBcdWM4MDFcdWQ3OGMgXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHViYTg1XHVjNmIwXHViMjk0IDNcdWM3NzQgXHVjODAxXHVkNzhjIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZmNcdWM2YjBcdWIyOTQgMlx1YWMwMCBcdWM4MDFcdWQ3OGMgXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWNlMCwgXHViYTg1XHVjNmIwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyAxXHVjNzc0IFx1YzgwMVx1ZDc4YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVhZGZjXHVjNmIwXHVjNjQwIFx1YmE4NVx1YzZiMFx1YjI5NCBcdWNkNWNcdWMxMjBcdWM3NTggXHVjODA0XHViN2I1XHVjNzNjXHViODVjIFx1Yzc4NFx1ZDU4OFx1YzczY1x1YmE3MCwgXHVhZGZjXHVjNmIwXHVhYzAwIFx1YzViYlx1YjI5NCBcdWM4MTBcdWMyMThcdWIyOTQgNlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZTc0XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEgJmxlOyBOICZsZTsgMSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIGlcdWJjODhcdWM5ZjhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxOFx1YjI5NCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgaVx1YmM4OFx1YzlmOFx1YzVkMCBcdWIxOTNcdWM3NzggXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCAxXHVjNzc0XHVjMGMxIDEwLDAwMFx1Yzc3NFx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWRmY1x1YzZiMFx1YzY0MCBcdWJhODVcdWM2YjBcdWFjMDAgXHVjZDVjXHVjMTIwXHVjNzU4IFx1YzgwNFx1YjdiNVx1YzczY1x1Yjg1YyBcdWM3ODRcdWQ1NjAgXHViNTRjIFx1YWRmY1x1YzZiMFx1YWMwMCBcdWM1YmJcdWFjOGNcdWI0MThcdWIyOTQgXHVjODEwXHVjMjE4XHViOTdjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMDYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FyZCBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5BbGljZSBpcyBwbGF5aW5nIGEgc2ltcGxlIGJ1dCBpbnRlcmVzdGluZyBjb21wdXRlciBnYW1lIG9uIGhlciBjb21wdXRlci4gVGhlIGdhbWUgcGxheXMgYXMgZm9sbG93czogd2hlbiBBbGljZSBzdGFydHMgdGhlIGdhbWUsIHRoZSBjb21wdXRlciBzaG93cyBuIGNhcmRzIG9uIHRoZSBtb25pdG9yIGluIGEgbGluZS4gRWFjaCBjYXJkIGlzIGFzc29jaWF0ZWQgd2l0aCBhIG51bWJlciBwcmludGVkIG9uIHRoZSBmYWNlIGFuZCBhbGwgdGhlIGNhcmRzIGFyZSBmYWNlZCB1cCBzbyB0aGF0IHNoZSBjYW4gc2VlIGV2ZXJ5IG51bWJlciBwcmludGVkIG9uIHRoZSBjYXJkcy4gU2hlIGFuZCB0aGUgY29tcHV0ZXIgcmVwZWF0ZWRseSBwaWNrIHVwIGEgY2FyZCBpbiB0dXJuIGVpdGhlciBmcm9tIHRoZSBmcm9udCBvciBmcm9tIHRoZSByZWFyIG9mIHRoZSBsaW5lIHVudGlsIHRoZXJlIGlzIG5vIGNhcmQgaW4gdGhlIGxpbmUuIFNoZSBhbHdheXMgc3RhcnRzIHRoZSBnYW1lLiBJbiBvdGhlciB3b3Jkcywgc2hlIGFsd2F5cyBwaWNrcyB1cCBhIGNhcmQgZmlyc3QuIFRoZSBnb2FsIG9mIHRoZSBnYW1lIGZvciBBbGljZSBpcyB0byBtYXhpbWl6ZSB0aGUgc3VtIG9mIGFsbCB0aGUgbnVtYmVycyBwcmludGVkIG9uIHRoZSBjYXJkcyBzaGUgcGlja3MgdXAuIFNoZSBjb21wbGV0ZWx5IHVuZGVyc3RhbmRzIGEgc3RyYXRlZ3kgdG8gbWFrZSB0aGUgc3VtIG1heGltaXplZC4gRGVmaW5pdGVseSB0aGUgY29tcHV0ZXIgd2lsbCBwcmV2ZW50IEFsaWNlIGZyb20gbWFraW5nIGl0LjxcL3A+XHJcblxyXG48cD5IZXJlIGlzIGFuIGV4YW1wbGUuIFRoZXJlIGFyZSBmb3VyIGNhcmRzIGluIGEgbGluZSBhbmQgbnVtYmVycyBvbiB0aGUgY2FyZHMgYXJlICg0LCAzLCAxLCAyKS4gQWxpY2UgZmlyc3QgcGlja3MgdXAgdGhlIGNhcmQgb2YgbnVtYmVyIDQgZnJvbSB0aGUgZnJvbnQgb2YgdGhlIGxpbmUuIFRoZW4gdGhlIGNvbXB1dGVyIHBpY2tzIHVwIHRoZSBjYXJkIG9mIG51bWJlciAzIGZyb20gdGhlIGZyb250LiBUaGVuIEFsaWNlIHBpY2tzIHVwIHRoZSBjYXJkIG9mIG51bWJlciAyIGZyb20gdGhlIHJlYXIuIEZpbmFsbHksIHRoZSBjb21wdXRlciBwaWNrcyB1cCB0aGUgbGFzdCBjYXJkIG9mIG51bWJlciAxLiBUaGlzIGlzIHRoZSBiZXN0IHBpY2tpbmcgb3JkZXIgZm9yIGJvdGggQWxpY2UgYW5kIHRoZSBjb21wdXRlciwgYW5kIEFsaWNlIG1ha2VzIHRoZSBzdW0gNi48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byBtYWtlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHRoZSBzdW0gb2YgYWxsIHRoZSBudW1iZXJzIG9uIHRoZSBjYXJkcyBBbGljZSBzZWxlY3RzIGFtb25nIGdpdmVuIG4gY2FyZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyLCBuICgxICZsZTsgbiAmbGU7IDEsMDAwKSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIGNhcmRzLiBJbiB0aGUgZm9sbG93aW5nIGxpbmUsIG4gbnVtYmVycyBhcmUgZ2l2ZW4gZWFjaCBvZiB3aGljaCBkZW5vdGVzIHRoZSBudW1iZXIgcHJpbnRlZCBvbiB0aGUgY2FyZHMgYW5kIGlzIHNlcGFyYXRlZCBieSBhIGJsYW5rLiBFYWNoIG51bWJlciBwcmludGVkIG9uIHRoZSBjYXJkcyBpcyBiZXR3ZWVuIDEgYW5kIDEwLDAwMCwgaW5jbHVzaXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhIG51bWJlciB3aGljaCByZXByZXNlbnRzIHRoZSBzdW0gb2YgYWxsIHRoZSBudW1iZXJzIHByaW50ZWQgb24gdGhlIGNhcmRzIEFsaWNlIHNlbGVjdHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d