3835. [雅礼集训 2017 Day10] 数列

【题目描述】

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

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

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

【输入格式】

第一行一个整数 $N$ 。

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

【输出格式】

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

【样例1输入】

2
1 1

【样例1输出】

1 4

【样例2输入】

4
2 1 3 4

【样例2输出】

4 1

【样例3】

点击下载样例3 

【数据规模与约定】

对于 $30\%$ 的数据， $N \leq 20$ ；

对于 $50\%$ 的数据， $1 \leq N \leq 1000$ ；

对于 $100\%$ 的数据， $1 \leq N \leq 200000，初始数列元素 S_i \lt 10^9$ 。