25090번 - 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 $dk$ 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 $N$ dice. The $i$-th die is a $dS_i,ドル that is, it has $S_i$ sides showing integers 1ドル$ through $S_i$. A straight of length $l$ starting at $x$ is the list of integers $x,x+1,\dots ,x+(l-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, $T$. $T$ test cases follow. Each test case is described in two lines. The first line of a test case contains a single integer $N,ドル the number of dice in the game. The second line contains $N$ integers $S_1,S_2, \dots ,S_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.

제한

• 1ドル≤T≤100$.

Test Set 1 (9점)

시간 제한: 5 초

• 1ドル≤N≤10$.
• 4ドル≤S_i≤20,ドル for all $i$.

Test Set 2 (11점)

시간 제한: 15 초

• 1ドル≤N≤10^5$.
• 4ドル≤S_i≤10^6,ドル for all $i$.

힌트

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 55 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.