스파이더맨의 운동

스파이더맨은 매일 등반 운동을 한다. 정해진 거리만큼 오르내린 뒤 잠깐 쉬고, 다시 오르내리기를 반복한다. 운동은 거리의 수열 $d_1, d_2, \ldots, d_m$ 으로 주어지며, $d_i$ 는 $i$ 번째 구간에서 오르내려야 하는 거리(미터)다. 각 구간에서 위로 오르든 아래로 내려가든 운동 효과는 같지만, 그는 시작과 끝이 모두 지면(높이 0)이 되도록 어떤 구간은 오르고 어떤 구간은 내려가고 싶어 한다. 단, 그의 발은 절대 지면 아래로 내려갈 수 없다.

또한 그는 되도록 낮은 건물을 쓰고 싶어 한다(사실은 고소공포증이 있다). 건물은 운동 중 그의 발이 닿는 가장 높은 지점보다 최소 2미터는 더 높아야 한다.

각 구간에서 언제 오르고 언제 내려갈지 정해 필요한 건물 높이를 최소로 만들어야 한다. 유효한 방법은 시작과 끝이 모두 지면(0미터)이어야 하고, 도중에 지면 아래로 내려가서는 안 되며, 거리들의 순서는 바꿀 수 없다.

예를 들어 거리가 $20\ 20\ 20\ 20$ 이면 올라가고-올라가고-내려가고-내려가는 방법은 42미터 건물이 필요하지만, 올라가고-내려가고-올라가고-내려가는 방법은 22미터 건물이면 충분해 최적이다. 어떤 수열은 유효한 방법이 아예 없을 수도 있다(예: $3\ 4\ 2\ 1\ 6\ 4\ 5$).

첫 줄에 시나리오의 개수 $N$ 이 주어진다. 이어지는 $2N$ 개의 줄이 시나리오를 한 개당 두 줄씩 기술한다. 각 시나리오의 첫 줄에는 거리의 개수인 양의 정수 $M\ (1 \le M \le 40)$ 이, 둘째 줄에는 $M$ 개의 양의 정수 거리가 공백으로 구분되어 주어진다. 한 시나리오에서 거리의 총합은 최대 1000이다.

각 시나리오마다 한 줄을 출력한다. 유효한 방법이 존재하면 필요한 건물의 최소 높이(정수 하나)를 출력하고, 존재하지 않으면 문자열 IMPOSSIBLE 을 출력한다.