9448 - 最长递增子序列

给定正整数序列 x1xnx_1 \sim x_n,以下递增子序列均为非严格递增(不允许相等)。

计算其最长递增子序列的长度 ss

计算从给定的序列中最多可取出多少个长度为 ss 的递增子序列。

如果允许在取出的序列中多次使用 x1xnx_1 和 x_n,则从给定序列中最多可取出多少个长度为 s 的递增子序列。

输入

文件第 1 行有 1 个正整数 n,表示给定序列的长度。接下来的 1 行有 n 个正整数 x1xnx_1 \sim x_n

输出

第 1 行是最长递增子序列的长度 ss

第 2 行是可取出的长度为 ss 的递增子序列个数。

第 3 行是允许在取出的序列中多次使用 x1x_1xnx_n 时可取出的长度为 ss 的递增子序列个数。

样例

输入
复制

4
3 6 2 5

输出
复制

2
2
3

提示

1n5001 \leq n \leq 500

来源

模板

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题