Spiderman's Workout

Interview

Time limit1sMemory limit128 MB

Summary

Assign plus or minus signs to the distances so the partial sums stay at or above 0 and return to 0 at the end, minimizing the peak height.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Implementation, Math
Solved: No attempts yet

Problem

Staying fit matters to every super hero, and Spiderman is no exception. Each day he does a climbing workout: he climbs a fixed distance, rests, climbs again, rests again, and so on. The workout is given as a sequence of distances $d_1, d_2, \ldots, d_m$ , where $d_i$ is how many meters he moves up or down during the $i$ -th stage. For each stage it makes no difference to the workout whether he goes up or down, but he wants to choose a direction for every stage so that he both starts and finishes at street level (height 0). His feet may never go below street level.

He also wants to use as low a building as possible (secretly, he is afraid of heights). The building must be at least 2 meters taller than the highest point his feet reach during the workout.

Decide when he should go up and when he should go down so that the required building height is minimized. A valid climb must start and end at street level (0 meters), must never go below street level, and may not reorder the distances.

For example, with distances $20\ 20\ 20\ 20$ , going up, up, down, down needs a 42-meter building, while up, down, up, down needs only a 22-meter building and is optimal. Some sequences admit no valid climb at all (for instance $3\ 4\ 2\ 1\ 6\ 4\ 5$ ).

Input

The first line contains an integer $N$ , the number of scenarios. The next $2N$ lines describe the scenarios, two lines each: the first line gives a positive integer $M\ (1 \le M \le 40)$ , the number of distances, and the second line contains the $M$ positive integer distances separated by spaces. In any scenario the total of the distances is at most 1000.

Output

For each scenario output a single line. If a valid climb exists, output the minimum required building height (a single integer); otherwise output the string IMPOSSIBLE.

Examples3

Example 1

Input

3
4
20 20 20 20
6
3 2 5 3 1 2
7
3 4 2 1 6 4 5

Expected output

22
7
IMPOSSIBLE

Example 2
Input
```
1
2
10 10
```
Expected output
```
12
```

Example 3

Input

3
2
7 7
2
4 6
6
3 2 5 3 1 2

Expected output

9
IMPOSSIBLE
7