The Election Day
And it is the day of the election. The Election Commission has set up a unique voting system this time to enhance security and complete the proceedings in a timely manner. There are N voters in the country and all of them assemble in a large queue. The queue has polling booths at each of its end. Now each voter needs some time to think about his precious vote. The ith voter takes exactly think[i] seconds inside the polling booth to cast his vote. Obviously he cannot think while he is in queue because the people have grown very smart and can figure out what is going in each others mind by just looking at the faces.
At any given second, a person can do the following activities :
- He may move to one of the adjacent cells in the queue(left or right) provided the cell exist and it is unoccupied then. No two people can stand on the same cell of the queue at the same time.
- He may enter the polling booth and start to think.
- He may leave the polling booth and go to his home.
Note that people walk simultaneously, so a person can enter any cell or the booth at the same time another person leaves it.
Given the array think[ ], you need to determine the shortest possible time in which all people have cast their votes.
The first line of the input consists of the number of cases (T). T test cases follows. Each test case begins with line with the number of people (N). Next line contains N numbers which constitute the array think. 0th index is the leftmost person and (N - 1)th index is the rightmost.
For each test case, output one number which is the shortest time in which election is completed and all people go back to their homes.
T ≤ 50
1 ≤ N ≤ 105
0 ≤ think[i] ≤ 103
2 3 3 4 2 2 4 0
In the first test case, things happen in the following manner: Let person A be on cell 0, B be on cell 1 and C be on cell 2 initially. Also lets denote left polling booth as L and right polling booth as R.
- Time 0 : A on 0, B on 1, C on 2. L and R empty
- Time 1 : A in L, C in R, B on 2.
- Time 3 : C casts its vote
- Time 4 : C leaves R, B enters R.
- Time 5 : A leaves L and goes home.
- Time 8 : B gives vote
- Time 9 : B leaves for home
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions