You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

P2687 加强版。在本题中，$N\leq 10^6$，且输出方案数需要对 $10^9+7$ 取模。

题目描述

“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀：“逢低吸纳，越低越买”。

这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低。按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。

给定连续的 $N$ 天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票，和最优方案数对 $10^9+7$ 取模的结果。

以下面这个表为例，某几天的股价是：

这个例子中，如果每次买股票时的股价都比上一次买时低，那么最多能买 $4$ 次股票。一种买法如下（可能有其他的买法）：

输入格式

第 $1$ 行：一个整数 $N$，表示能买股票的天数。

以后多行，输入 $N$ 个非负整数（可能分多行），第 $i$ 个正整数表示第 $i$ 天的股价。这些非负整数大小不会超过 $2^{32}-1$。

输出格式

一行两个整数，表示按每次买股票时的股价都比上一次买时低的要求最多能够买进股票的天数，和能够买进这些天数的股票的股票购买方案数量，对 $10^9+7$ 取模。

两个方案不相同当且仅当这两个方案中所购买的股票的价格序列不相同。

12
68 69 54 64 68 64 70 67
78 62 98 87

4 2

提示

$1 \le N \le 10^6$。