Problem Description
Yifenfei and lemon are good friends, they don’t like Ctw, because Ctw’s name is so worldliness.
One day Lcy give them a lot of jewel. Each jewel has own value. They put the jewels in a line, and don’t swap the position of jewel. In order to division the jewels, they think a lot of ideas. At last, they decide a way to division by voting. First let Ctw to divide the line into two non-empty sublines (each subline express a group of jewel). Second yifenfei will to divide one of sublines and also divide it into two non-empty sublines. Than let lemon to choose one of this three sublines., than yifenfei choose one of remaining subline. At last Ctw hold the last subline..
Every one wants to maximize their own share. But because yifenfei don’t like Ctw, so if there are two divisions let himself get the some value, he will choose the way let Ctw get smaller values.
Assuming every one have full knowledge of each other’s strategies and make their decision optimally.
Input
The input contains multiple test cases.
Each test case include, first one integers n. (3<=n<=100), express how many jewels.
Next one line include n integers Vi (Vi<2^31). The order of jewel is according the position in the line..
Output
For each test case output one integer that CTW is maximum value of jewels can get.
Sample Input
4
50 90 10 100
3
5 5 5
9
1 1 1 1 1 1 1 1 1
Sample Output
50
5
2
