Lord Cohen is a baron with the best-looking hedge in the country. His award-winning hedge consists of N bushes planted side by side in a straight line. The bushes are numbered left to right from 1 to N. The baron’s neighbours all cut their own hedges so that all of their bushes have the same height. But Lord Cohen has a secret key to his landscaping success. His gardener follows a special rule when trimming the hedge, which is why the baron’s hedge is always in its award-winning condition.

The rule is — to start on the left at bush #2 and move to the right. The gardener cuts the top of each bush to make it exactly as tall as the average of the two bushes on either side. If the bush is already as short as the average or shorter, then the gardener does not touch this bush and moves on to the next bush on the right, until the second-to-last bush. The baron is certain that this procedure is the key to success.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each one consists of two lines. The first line will contain an integer N, and the second line will contain N space-separated integers denoting the heights of the bushes, from bush #1 to bush #N.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is the height of bush number N – 1 after the gardener has finished trimming the hedge according to the baron’s special procedure.

Answers with a relative error of at most 10-4 will be considered correct. See the FAQ for an explanation of what that means, and what formats of floating-point numbers we accept.

Limits

1 ≤ T ≤ 100.

Each height will be an integer betwween 1 and 1000, inclusive.

Small dataset

3 ≤ N ≤ 10.

Large dataset

3 ≤ N ≤ 1000.

Sample:

Input Output 6 5 1 2 3 6 7 Case #1: 5.000000 5 1 2 3 4 7 Case #2: 4.000000 3 7 7 7 Case #3: 7.000000 5 7 8 7 9 9 Case #4: 8.000000 5 5 8 9 9 9 Case #5: 8.500000 6 1 2 2 2 2 2 Case #6: 1.937500

Key points to crack the problem:

- Hedge consists of N bushes planted side by side in a straight line. Bushes numbered left to right from 1 to N.
- Start on the left at bush #2 and move to the right
- Cut the top of each bush to make it exactly as tall as the average of the two bushes on either side
- If bush is already as short as the average or shorter then leave it and move to next one on the right until the second-to-last bush
- y is the height of bush number N-1 after the trimming
- Answers with a relative error of at most 10 to the power -4 will be considered correct.

**possible solution**

import java.io.*; import java.util.*; public class Hedgemony { static Scanner sc = new Scanner(System.in); public static void main(String[] args) throws IOException { // BufferedReader f = new BufferedReader(new FileReader("A-small-practice.in")); // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("A-small-practice.out"))); // int limit = 10; BufferedReader f = new BufferedReader(new FileReader("A-large-practice.in")); PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("A-large-practice.out"))); int limit = 1000; StringTokenizer st = new StringTokenizer(f.readLine()); int t = Integer.parseInt(st.nextToken()); if(t>=1 && t<=100){ for(int i=1; i<=t; i++){ st = new StringTokenizer(f.readLine()); int n = Integer.parseInt(st.nextToken()); double max_bush = 0.4d, new_bush = 0.4d, avg = 0.4d, bush=0.4d; double[] data = new double[n]; st = new StringTokenizer(f.readLine()); if(n>=3 && n<=limit){ for(int j=0; j<n; j++){ data[j] = Integer.parseInt(st.nextToken()); } for(int j=1; j<n-1; j++){ avg = (data[j-1] + data[j+1])/2; if(avg < data[j]){ data[j] = avg; } } } out.println("Case #"+ i+": " + data[n-2]); } } out.close(); System.exit(0); } }