问题 H: Alice and Bob

Given an sequence of $n$ elements a1,a2, $...$ ,an.

Alice and Bob will play a game alternating turns with Alice going first.

If the current sequence length is $n$, select a position $pos$ ($1\le pos<n$) to divide the sequence into two part. If the sum of all elements from the first position to the $pos$ position is less than the sum of all elements from the$pos+1$ position to the last position, then delete the first element to the$pos$ element. Otherwise, delete the $pos+1$ element to the $n$ element.

When the sequence length after a person's operation is $1$, that person wins.

Alice and Bob both want to win. If they can, they hope the element in the final sequence bigger. Otherwise, they hope the element in the final sequence smaller.

Find the answer if both Alice and Bob play optimally.

Each test contains multiple test cases. The first line contains the number of test cases $T$（$T\le 1000$）. The description of the test cases follows.

The first line contains one integer $n$（$1<n\le 3000$).

The second line contains $n$ integers a1, a2,…, an( 1≤ ai≤109).

It's guaranteed that $\sum n\le 10000$