Stack of Cylinders

Suppose you launch a set of cylinders, with different radius, over a hill, in such a way they get stacked like in the figure.

Accordingly to the radius of the cylinders, only a subset will be connected forming a continuous path. In the example represented, this path is composed by cylinders 2, 3 and 6. Cylinder 2 is the path head and cylinder 6 is the path tail.

The enclosing distance d is measured from the left support point of the path head until the right point of the path tail.

Example of a stack of cylinders.

Given a sequence of cylinders, this problem consists in the evaluation of the enclosing distance and the sequence of cylinders that compose the continuous path. It is ensured that each cylinder can touch no more than one cylinder at its left and no more than one cylinder at its right.

The first line of input is a single integer indicating the number of test cases. The test cases follow consecutively.

For each test case, the first text line contains the number NC (integer format) of cylinders. It is followed by a sequence of NC text lines containing, each line, a cylinder radius (integer or decimal format).

Note that the maximum number of cylinders for a test case is 100. Any radius will be greater than 0 and less than or equal to 1000.0.

For each test case, on a single line print the test case number as #N (start with 1), a ":", space, and d, the enclosing distance, described above, rounded to one decimal digit.

2
3
10
10
10
7
3
25
35
5
4
32
4

#1: 60.0
#2: 183.1