You are given an array of integers A_{1..N} of N elements.

A function F(i) of A returns the largest index j of array A such that all A_{k} where i < k < j are smaller than both A_{i} and A_{j}. By convention, j = N if i = N. Consider the following example. Let A_{1..6} = {5, 2, 3, 6, 4, 5}; then, function F(i) for i = 1..6 will return {4, 3, 4, 6, 6, 6}. Notice that:

- For i = 1, the largest j is 4. A
_{1}= 5, A_{4}= 6, and A_{2..3}= {2, 3}; therefore, F(1) = 4. - For i = 2, the largest j is 3. A
_{2}= 2, A_{3}= 3, and A_{ø}= { }—there are no integer k such that 2 < k < 3; therefore, F(2) = 3. - For i = 3, the largest j is 4. A
_{3}= 3, A_{4}= 6, and A_{ø}= { }; therefore, F(3) = 4. - For i = 4, the largest j is 6. A
_{4}= 6, A_{6}= 5, and A_{5..5}= {4}; therefore, F(4) = 6. - For i = 5, the largest j is 6. A
_{5}= 4, A_{6}= 5, and A_{ø}= { }; therefore, F(5) = 6. - For i = 6, j = 6 (by convention); therefore, F(6) = 6.

A function G(i) of A is defined as **F(i) - i**. Thus, in the previous example, G(i) for i = 1..6 is {3, 1, 1, 2, 1, 0}.

Your task in this problem is to output the largest G(i) and the sum of G(i) for all i given array A. In the previous example, the largest G(i) is 3, while the sum of all G(i) is 3 + 1 + 1 + 2 + 1 + 0 = 8.

As the sum of all G(i) can be very large, you should modulo the output by 1,000,000,007.

Input begins with an integer: T (1 ≤ T ≤ 20) denoting the number of cases.

*Each case contains the following input block:* Each case begins with an integer N (1 ≤ N ≤ 500,000) denoting the array size. The next line contains N integers A_{i} (1 ≤ A_{i} ≤ 1,000,000,000) representing the array's element.

The sum of all N in input is no larger than 1,000,000.

For each case, output in a line "Case #X: Y Z" where X is the case number (starts from 1), Y is the largest G(i), and Z is the sum of all G(i) modulo 1,000,000,007 for the respective case.

input | Example #1 |

4 6 5 2 3 6 4 5 5 1 2 3 4 5 5 5 4 3 2 1 4 100 130 125 147 | |

output | |

Case #1: 3 8 Case #2: 1 4 Case #3: 1 4 Case #4: 2 4 | |

explanation | |

Case 1: This is the example given in the problem statement. Case 2: F(i) = {2, 3, 4, 5, 5}; G(i) = {1, 1, 1, 1, 0}. Case 3: F(i) = {2, 3, 4, 5, 5}; G(i) = {1, 1, 1, 1, 0}. Case 4: F(i) = {2, 4, 4, 4}; G(i) = {1, 2, 1, 0}. |

*End of Problem*