숫자 뽑기 게임

아현이는 건반악기를 다뤄서 손가락 힘을 기르려고 손가락 끝으로 숫자를 뽑는 게임을 한다. 규칙은 다음과 같다.

아현이에게 양의 정수 리스트가 주어진다. 아현이는 리스트의 맨 앞과 맨 뒤를 뺀 나머지 숫자 중 하나를 고를 수 있다. 고른 숫자는 리스트에서 사라지고, 고른 숫자와 그 양옆 숫자의 합만큼 점수가 오른다. 리스트에 숫자가 두 개만 남으면 게임이 끝난다.

리스트가 1 2 3 4 5인 경우를 보자. 아현이가 3을 뽑으면 점수는 $2+3+4=9$가 되고 리스트에는 1 2 4 5가 남는다. 이어서 4를 뽑으면 점수는 $9+2+4+5=20$이 되고 리스트에는 1 2 5가 남는다.

리스트가 주어졌을 때 아현이가 받을 수 있는 가장 높은 점수를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 $n$ $k_1$ $k_2$ $\ldots$ $k_n$ 형식으로 주어진다. $n$은 리스트에 들어 있는 숫자의 개수이고 $3 \le n \le 200$이다. 각 정수 $k_i$는 $1 \le k_i \le 100$을 만족한다. 마지막 줄에는 $0$ 하나만 주어지며, 이 줄을 읽으면 입력이 끝난다.

각 테스트 케이스마다 아현이가 받을 수 있는 가장 높은 점수를 한 줄에 하나씩 출력한다.