#6048. 「雅礼集训 2017 Day10」数列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 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

数据范围与提示

对于 30\% 的数据, N \leq 20
对于 50\% 的数据, 1 \leq N \leq 1000
对于 100\% 的数据, 1 \leq N \leq 200000