시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 38 12 9 32.143%

문제

아현이는 건반악기를 다루기 때문에 손가락 힘을 기르기 위해 손가락 끝을 이용해 숫자를 뽑는 게임을 즐긴다. 그 게임의 방식은 이렇다.

아현이에게 양의 정수들의 리스트가 주어진다. 그리고 아현이는 리스트의 첫번째 혹은 마지막번째의 숫자를 제외한 어떤 숫자를 선택할 수 있다. 아현이가 숫자를 선택했을 때, 그 숫자는 리스트에서 사라지고 아현이의 점수는 선택한 숫자와 이웃한 숫자들의 합에 의해 올라간다.

예를 들면 리스트에 1 2 3 4 5가 있다고 하자. 아현이가 3을 뽑으면 아현이의 점수는 2+3+4 = 9 점이 된다. 그 다음 1 2 4 5가 남은 상태에서 4를 뽑는다면, 아현이의 점수는 9+2+4+5 = 20 점이 되고 리스트에는 1 2 5가 남게된다. 이 게임은 리스트에 2개의 숫자만 남았을 때 끝난다.

숫자 리스트가 주어졌을 때, 아현이가 받을 수 있는 가장 높은 점수는 몇점일까?

입력

입력은 많은 테스트케이스로 구성된다. 입력 형식은 n k1 k2 ... kn 이며 , n (n ≤ 200) 은 리스트의 숫자의 개수이고 각각의 정수 ki의 범위는 1 ≤ ki ≤ 100 와 같다. 모든 테스트 케이스에서 n ≥ 3 이며, n=0 일 때 입력을 받는 것을 종료한다.

출력

각각의 케이스에 따라 받을 수 있는 최고 점수를 출력한다.

예제 입력

5 1 2 3 4 5
5 2 1 5 3 4
6 30 20 40 50 70 60
0

예제 출력

30
31
570

힌트