P12981 [GCJ 2022 Qualification] d1000000

While the most typical type of dice have 6 sides, each of which shows a different integer 1 through 6, there are many games that use other types. In particular, a $d_k$ is a die with $k$ sides, each of which shows a different integer 1 through $k$. A $d6$ is a typical die, a $d4$ has four sides, and a $d1000000$ has one million sides.  In this problem, we start with a collection of $\mathbf{N}$ dice. The $i$-th die is a $d\mathbf{S}_i$, that is, it has $\mathbf{S}_i$ sides showing integers 1 through $\mathbf{S}_i$. A straight of length $\ell$ starting at $x$ is the list of integers $x$, $x + 1$, $\cdots$, $x + (\ell - 1)$. We want to choose some of the dice (possibly all) and pick one number from each to form a straight. What is the longest straight we can form in this way?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case is described in two lines. The firstline of a test case contains a single integer $\mathbf{N}$, the number of dice in the game. The second line contains $\mathbf{N}$ integers $\mathbf{S}_1$, $\mathbf{S}_2$, $\cdots$, $\mathbf{S}_\mathbf{N}$, each representing the number of sides of a different die.

For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of input dice that can be put in a straight.

**Sample Explanation** In Sample Case #1, there are multiple ways to form a straight using all $4$ dice. One possible way is shown in the image above. In Sample Case #2, since none of the dice can show an integer greater than $5$, there is no way to have a straight with more than $5$ dice. There are multiple ways to form a straight with exactly $5$ dice. For example, pick the integers $4$ and $5$ for both $d5$'s and then integers $1, 2$, and $3$ for three of the $d4$'s to form $1, 2, 3, 4, 5$. In Sample Case #3, it is possible to form the straight $1, 2, 3, 4, 5, 6, 7, 8, 9$ by discarding one $d4$ and using the $d4$'s, $d5$, and $d6$ to get $1$ through $4$; the $d7$'s to get $5$ through $7$; and the $d10$'s to get $8$ and $9$. There is no way to form a straight of length $10$, so this is the best that can be done. In Sample Case #4, we can only form a straight of length $1$, but we can do so by picking any integer for the $d10$ we are given. **Limits** - $1 \leq \mathbf{T} \leq 100$. **Test Set 1 (9 Pts, Visible Verdict)** - $1 \leq \mathbf{N} \leq 10$. - $4 \leq \mathbf{S}_i \leq 20$, for all $i$. **Test Set 2 (11 Pts, Visible Verdict)** - $1 \leq \mathbf{N} \leq 10^5$. - $4 \leq \mathbf{S}_i \leq 10^6$, for all $i$.