← 返回题目
题库练习 「雅礼集训 2017 Day10」数列
← 上一题 下一题 →

A6670 | 「雅礼集训 2017 Day10」数列

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

小 A 有 $ N $ 个正整数，紧接着，他打算依次在黑板上写下这 $ N $ 个数。对于每一个数，他可以决定将这个数写在当前数列的最左边或最右边。现在他想知道，他写下的数列的可能的最长严格上升子序列（可由不连续的元素组成）的长度是多少，同时他还想知道有多少种不同的最长的严格上升子序列。

两个子序列被认为是不同的，当且仅当：两个子序列属于两个不同的写序列的方案（两个写序列中有至少一步是不一样的）或两个子序列位于同一写序列方案的不同位置。

由于结果可能很大，所以小 A 只需要知道最长严格上升子序列的方案数对 $ 10 ^ 9 + 7 $ 取模的结果。

输入格式

第一行一个整数 $ N $。
第二行 $ N $ 个正整数，表示小 A 写下的初始序列。

输出格式

输出一行两个整数，最长严格上升子序列的长度以及方案数模 $ 10 ^ 9 + 7 $ 后的结果。

输入输出样例

输入 #1
2
1 1
输出 #1
1 4
输入 #2
4
2 1 3 4
输出 #2
4 1
C++ 编辑器
输入
输出