Background

An enhanced version of P2687. In this problem, $N \le 10^6$, and the number of plans needs to be taken modulo $10^9+7$.

Problem Description

“Buy low” is a successful rule of thumb in stock trading. If you want to become a successful investor, you should follow this rule: “buy low, and the lower it gets, the more you buy.”

This means: each time you buy a stock, the price must be lower than the price when you bought last time. The more times you can buy under this rule, the better. Find the maximum number of times you can buy under this rule.

Given the stock prices over $N$ consecutive days, you may buy at most once on any day, but the price when you buy must be lower than the price when you bought previously. Write a program to compute the maximum number of times you can buy, and the number of optimal plans modulo $10^9+7$.

For example, the stock prices on some days are:

In this example, if each time you buy the stock the price is lower than the last time, you can buy at most $4$ times. One possible way to buy is (there may be other ways):

Input Format

Line $1$: an integer $N$, the number of days on which you can buy stocks.

The following lines contain $N$ non-negative integers (possibly across multiple lines). The $i$-th positive integer represents the stock price on day $i$. These non-negative integers will not exceed $2^{32}-1$.

Output Format

Output one line with two integers: the maximum number of days on which you can buy stocks while ensuring that each purchase price is lower than the previous purchase price, and the number of purchase plans that achieve this maximum, taken modulo $10^9+7$.

Two plans are different if and only if the sequences of purchased stock prices in the two plans are different.

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

4 2

Hint

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

Translated by ChatGPT 5