시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB33221565.217%

문제

Initially, we have a given sequence a1,a2,a3,...,an. In each step, we can take any two adjacent integers ai and ai+1 and replace them with max(ai,ai+1), thus resulting in a shorter sequence. The cost of this operation is max(ai,ai+1). After n-1 such steps, the sequence length becomes 1. Given a sequence, your task is to calculate the minimal cost required to make that sequence of length 1. 

입력

The first line has a positive integer T, T <= 100,000, denoting the number of test cases. This is followed by each test case per line. 

Each test case consists of two lines. The first line contains a single integer N as the length of the sequence. N is between 2 and 5000 inclusive The next line contains N integers separated by a single space. Each of the numbers in the sequence is between 1 and 100,000 inclusive. 

출력

For each test case, the output contains a line in the format Case #x: R, where x is the case number (starting from 1) and R is minimal cost to reduce the given sequence to a sequence of length 1. 

예제 입력 1

10
6
15 9 8 13 19 17
7
12 15 13 8 12 9 7
8
8 12 14 10 14 18 15 13
9
12 8 3 1 1 1 5 4 7
8
1 6 4 3 2 4 1 6
8
15 16 15 10 18 22 19 22
9
14 9 14 17 21 23 18 17 14
8
13 12 11 5 1 1 6 1
6
8 4 2 1 1 1
8
9 11 12 8 10 11 6 9

예제 출력 1

Case #1: 75
Case #2: 76
Case #3: 105
Case #4: 42
Case #5: 33
Case #6: 131
Case #7: 147
Case #8: 54
Case #9: 16
Case #10: 76