A certain forest has **N** trees growing in it, and there just so happens to
be a Fox living at the top of each one! The trees are numbered from 1 to
**N**, and their bases are all arranged in a straight line on the ground, with
1 metre between the bases of each pair of adjacent trees _i_ and _i_ \+ 1.
Each tree _i_ is **Hi** metres tall.

The Foxen are all good friends with one another, and frequently like to go out
for strolls to visit each other's homes. Rather than jumping directly between
the trees, they prefer to always keep their paws firmly planted on some
surface, such as tree trunks or the ground. As such, the shortest possible
trip from the top of tree _i_ to the top of another tree _j_ requires climbing
down tree _i_ to the ground, walking along the ground to the base of tree _j_,
and then climbing up to its top, resulting in a total distance of **Hi** \+
|_j_ \- _i_| + **Hj** metres traveled.

However, the Foxen aren't terribly satisfied with how long their trips
currently take. Given the frequency of their strolls, they've decided to
invest in reducing their travel distance by constructing some bridges between
the tree trunks. They're only interested in building metre-long, horizontal
bridges. Each bridge may be constructed to connect any pair of adjacent trees
_i_ and _i_ \+ 1, and it may be placed at any height above the ground, as long
as it touches both of those tree trunks (in other words, its height must be no
larger than the minimum of **Hi** and **Hi+1**). Multiple bridges may be
constructed at different heights between any given pair of adjacent trees.
Once bridges are installed, the Foxen will be willing to walk across them,
potentially saving them the time of descending all the way to the ground
during their strolls.

There are **N** * **(N - 1)** / 2 different pairs of Foxen _i_ and _j_ who
might want to meet up, requiring a trip to be taken from the top of tree _i_
to the top of tree _j_ (or vice versa). The Foxen's top priority is minimizing
the sum of the **N** * **(N - 1)** / 2 pairwise shortest distances of strolls
which would be required for these visits to take place. Please help them
determine the minimum possible value of this sum, assuming that they construct
as many bridges as it takes. That being said, they don't want to spend all day
constructing bridges either... as such, they're also interested in the minimum
number of bridges which they can construct to achieve that minimum possible
sum of pairwise distances.

### Input

Input begins with an integer **T**, the number of forests. For each forest,
there are two lines. The first line contains the integer **N**. The second
line contains **N** space-separated integers, the _i_th of which is the
integer **Hi**.

### Output

For the _i_th forest, print a line containing "Case #**i**: " followed by two
integers: the minimum possible sum of pairwise shortest distances after any
number of bridges are built (in metres), and the minimum number of bridges
required to achieve that minimum sum.

### Constraints

1 ≤ **T** ≤ 30
2 ≤ **N** ≤ 500,000
1 ≤ **Hi** ≤ 10,000,000
The sum of **N** values across all **T** cases does not exceed 6,000,000.

### Explanation of Sample

In the first case, the Foxen's optimal strategy is to construct one bridge
between the first 2 trees at a height of 20m, and another bridge between the
last 2 trees at a height of 10m. With this configuration, the shortest path
between the first 2 trees' tops is 11m long, as is the shortest path for the
last 2 trees. The shortest path between the first tree's top and the last
tree's top is 22m long. The resulting sum of pairwise shortest distances is
then 44m, which is the minimum possible sum.