Description

A farm has a non-circular fence consisting of $n$ posts arranged in order by their indices. We want to select some posts such that, when kept in their original index order, the selected posts' heights form a non-decreasing sequence. A non-decreasing sequence means every number in the sequence is not less than any number before it. Write a program to select posts so that the number of selected posts $t$ is maximized, and compute the total number of selection schemes $c$ that achieve $t$ posts.

Input Format

The first line contains a single integer $m$, indicating that there are $m$ test cases.
Each test case is given on one line as $n$ followed by $n$ integers $h_1, h_2, h_3, \dots, h_n$ (where $h_i$ denotes the height of the $i$-th post), all separated by spaces.

Output Format

For each test case, output $t$ and $c$. Print one test case per line, with $t$ and $c$ separated by a space.

3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12

4 1
2 2
3 3

Hint

$m \leq 5$，$n \leq 20$，$h_i \leq 150$.

Translated by ChatGPT 5