Server Time: Mon Oct 26, 2020 6:22 am
 Welcome ( logout )
F - Neighbor House (II)
 PDF (English) Ranklist
 Time Limit: 2 second(s) Memory Limit: 32 MB

A soap company wants to advertise their product in a local area. In this area, there are n houses and the houses are placed in circular fashion, such that house 1 has two neighbors: house 2 and n. House 5 has two neighbors: house 4 and 6. House n has two neighbors, house n-1 and 1.

Now the soap company has an estimation of the number of soaps they can sell on each house. But for their advertising policy, if they sell soaps to a house, they can't sell soaps to its two neighboring houses. No your task is to find the maximum number of estimated soaps they can sell in that area.

# Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (2 ≤ n ≤ 1000). The next line contains n space separated integers, where the ith integer denotes the estimated number of soaps that can be sold to the ith house. Each of these integers will lie in the range [1, 1000].

# Output

For each case, print the case number and the maximum number of estimated soaps that can be sold in that area.

# Output for Sample Input

3

2

10 100

3

10 2 11

4

8 9 2 8

Case 1: 100

Case 2: 11

Case 3: 17

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan