大样例下载

题目描述

给出一个整数序列 A，含有 n 个元素。

问：

(1) A 的最长严格下降子序列的长度

(2) A 有多少个不同的最长严格下降子序列。

注：如果两个子序列 S 和 T 不同，当且仅当满足以下两个条件之一：

（1）长度不同；

（2）存在一个 i 满足 Si ≠ Ti

输入格式

第一行：一个整数 n

接下来是 n 个整数 $A_i$，可能分布在若干行。

输出格式

一行：两个整数，分别表示最长严格下降子序列的长度、子序列数，中间以一个空格隔开。

样例输入

6
5 2 0 5
2 1

样例输出

3 2

样例解释

最长严格下降子序列的长度为 3，有两个：

5, 2, 0

5, 2, 1

数据范围

100% 的数据：$1 ≤ n ≤ 5000； 0 ≤ A_i < 2^{31}$