Sum of LIS lengths over every consecutive subsequence

Time limit1sMemory limit128 MB

Summary

Sum the LIS lengths of all contiguous subarrays for each test case of distinct integers.

Level: Medium6 of 10
Topics: Dynamic programming, Binary search, Brute force
Solved: No attempts yet

Problem

Mr. C is interested in the longest increasing subsequence problem. A sequence $S = s_1, s_2, \ldots, s_N$ is given. A subsequence $L = l_1, l_2, \ldots, l_k$ of $S$ is increasing when $l_1 < l_2 < \cdots < l_k$ , and the longest increasing subsequence of $S$ is its LIS.

A consecutive subsequence of $S$ is a subsequence whose elements are adjacent in the original sequence. Find the LIS length of every consecutive subsequence of non-zero length, then add all of those lengths together.

Input

The first line contains an integer $T$ , the number of cases. It is followed by $T$ blocks, each one case.

The first line of each case contains an integer $N$ ( $1 \le N \le 500$ ), the length of $S$ .

The next $N$ lines each contain an integer $s_i$ ( $1 \le s_i \le N$ ), the $i$ -th element of $S$ . Every element of $S$ is distinct.

Output

Print $T$ lines, one per case, in the same order as the input.

The $i$ -th line has the format Case #i: X, where $i$ is the case number and $X$ is the total LIS length over every consecutive subsequence of non-zero length in that case.

Examples1

Example 1
Input
```
1
3
3
1
2
```
Expected output
```
Case #1: 8
```