정수 개가 왼쪽부터 의 순서로 나열되어 있다. 이 수열에 다음 작업을 할 수 있다.
삭제한 원소는 사라지고, 나머지 원소의 순서는 그대로 유지된다. 값의 변화는 바로 이웃한 원소뿐 아니라 해당 방향에 남아 있는 모든 원소에 적용되며, 작업할 때마다 누적된다.
예를 들어, 에서 가운데 원소 을 삭제하면 가 된다. 여기에서 오른쪽 원소 를 삭제하면 가 남는다.
원소가 하나만 남을 때까지 작업을 반복할 때, 마지막에 남는 값으로 가능한 최댓값을 구하여라.
처음 주어지는 값, 작업 도중의 값, 마지막에 남는 값은 모두 음수일 수도 있다. 이면 작업을 하지 않고 처음의 원소가 그대로 남는다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 마지막에 남는 값으로 가능한 최댓값을 한 줄에 출력한다.
첫 번째 테스트 케이스에서는 지문에서 설명한 순서로 삭제하면 가 남으며, 이보다 큰 값을 남길 수는 없다.
두 번째 테스트 케이스에서는 이미 원소가 하나이므로 작업을 하지 않는다.
세 번째 테스트 케이스에서는 왼쪽 원소 을 삭제하면 이 된다. 여기에서 오른쪽 원소 을 삭제하면 이 남으며, 이것이 최댓값이다.
는 테스트 케이스의 개수이다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
첫째 줄에 수열의 길이 이 주어진다. 둘째 줄에 수열의 원소가 왼쪽부터 공백으로 구분되어 주어진다.
| 4 | 42 | 추가적인 제약이 없다. |
네 번째 테스트 케이스에서는 맨 오른쪽 원소를 세 번 삭제하면 수열이 차례로 , , 가 된다. 가능한 최댓값도 음수일 수 있다.
이 예제는 서브태스크 , , 의 조건을 만족한다.
