Fusing Weapons

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has recently started becoming a fan of computer games. He is currently playing a game in which he controls a warrior who is fighting evil monsters.
Before the start of each stage, N weapons appear on the screen in circular order. Each weapon has an integer associated with it, which represents its level. The chef can choose two adjacent weapons of the same level and fuse them into a single weapon of level A+1, where A is the level of the weapons before fusing. Both the old weapons will disappear and the new weapon will be placed in the place of the old weapons, shrinking the circle.
Chef can fuse as many times as he wants, and in each stage, he wants to make a weapon with as high a level as possible. Each stage is independent of other stages.
Please help Chef by figuring out the maximum level of a weapon that he can get in each stage.
Input
The first line contains integer T, denoting the number of stages. The description of each stage follows.
The first line of each stage's description contains an integer N, denoting the number of weapons.
The second line contains N spaceseparated integers: L_{1}, L_{2}, ..., L_{N}, where L_{i} is the level of the ith weapon. The ith and (i+1)th weapons are adjacent for all i which satisfy 1 ≤ i < N. Additionally, the first and Nth weapons are also adjacent.
Output
For each stage, output a single integer in new line, which should be the maximum level of a weapon that Chef can get.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 200,000
 1 ≤ sum of N in all stages ≤ 200,000
 1 ≤ L_{i} ≤ 200,000
Example
Input: 2 4 3 3 1 4 6 2 3 3 3 1 1 Output: 5 5
Explanation
Example case 1: The initial state is (3, 3, 1, 4). The Chef can fuse the first two weapons and get (4, 1, 4). Then he can fuse the first and last weapons to get (5, 1). Now, he can't do anything else. He has gotten a weapon of level 5, and you can show that there is no way to get a weapon of a higher level. Hence the answer is 5.
Example case 2: The initial state is (2, 3, 3, 3, 1, 1). The Chef can fuse the last two weapons and get the state (2, 3, 3, 3, 2). He can then fuse the first and fifth weapons and get (3, 3, 3, 3). Now, he can fuse the first and second to get (4, 3, 3). Then he fuses the second and third to get (4, 4). Finally, he fuses the first and second to get (5). You can check that nothing better can be achieved, and hence the answer is 5.
Author:  kingofnumbers 
Tags  kingofnumbers 
Date Added:  20102016 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 