Mushroom Monster (Large)

Kaylin loves mushrooms. Put them on her plate and she eats every last one. In this problem she is eating a plate of mushrooms while Bartholomew keeps adding more pieces to it.

We look at how many pieces of mushroom are on her plate at 10-second intervals. Bartholomew can put down any non-negative integer number of pieces at any moment, and the only way a piece leaves the plate is by being eaten.

Compute the minimum number of mushroom pieces Kaylin could have eaten under each of two assumptions.

1. Kaylin can eat any number of pieces at any moment.
2. Starting from the first time we look at the plate, Kaylin eats at a constant rate whenever there are mushrooms on her plate. The rate itself is not given, so it can be any value consistent with the observations.

Consider the observations 10 5 15 5.

Under the first assumption Kaylin ate at least 15 pieces: she eats 5, then 10 more pieces are put on the plate, then she eats another 10. There is no way to eat fewer.

Under the second assumption she ate at least 25 pieces. The rate has to be at least 1 piece per second. The plate starts with 10 pieces. In the first 10 seconds she eats 10 pieces and 5 more are put down. In the next 5 seconds she eats those 5 pieces, the plate then stays empty for 5 seconds, and Bartholomew puts down 15 pieces. She eats 10 pieces in the last 10 seconds.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case consists of two lines. The first line contains a single integer $N$, and the second line contains $N$ space-separated integers $m_i$, the number of mushroom pieces on the plate at the start and at every 10-second interval after that.

Limits

• $1 \le T \le 100$
• $2 \le N \le 1000$
• $0 \le m_i \le 10000$

For each test case, print one line in the form Case #x: y z, where $x$ is the test case number starting from 1, $y$ is the minimum under the first assumption, and $z$ is the minimum under the second assumption.