P2687 [USACO4.3] Buy on Dips — Buy Low, Buy Lower

It is intentional that using `long double` can pass this problem. For a strengthened version, see [P12930](https://www.luogu.com.cn/problem/P12930). In this problem, $N\leq 5000$.

“Buy on dips” is a successful tip for stock trading. If you want to be a successful investor, follow this tip: “Buy on dips, the lower the better.” This means: every time you buy, the stock price must be lower than the price at your previous purchase. The more times you can buy under this rule, the better. See how many times at most you can buy following this rule. You are given the price of the stock for each of $N$ consecutive days. You may buy once on any day, but the price at purchase must be lower than the price at your previous purchase. Write a program to find the maximum number of times you can buy. For example, suppose the prices on some days are: |Day |Price | |:-------|:-------| |$1$|$68$| |$2$|$69$| |$3$|$54$| |$4$|$64$| |$5$|$68$| |$6$|$64$| |$7$|$70$| |$8$|$67$| |$9$|$78$| |$10$|$62$| |$11$|$98$| |$12$|$87$| In this example, if each purchase price is lower than the previous one, you can buy at most $4$ times. One valid way is as follows (there may be others): |Day |Price | |:-------|:-------| |$2$|$69$| |$5$|$68$| |$6$|$64$| |$10$|$62$|

The first line: an integer $N$, the number of days on which you can buy. Then $N$ positive integers (possibly across multiple lines), where the $i$-th integer is the stock price on day $i$. Each integer does not exceed $2^{31}-1$.

One line with two integers: the maximum number of days you can buy under the rule that each purchase price is lower than the previous one, and the number of purchase plans that achieve this maximum. Two plans are different if and only if the sequences of purchased prices are different.

$1 \le N \le 5000$. Translated by ChatGPT 5