Description

The advice “buy low” is half the rule for success in the cow stock market. To be considered a great investor, you must follow this advice: “buy low; buy lower.” Each time you buy a stock, you must buy it at a price lower than the last time you bought it. The more times you buy, the better. Your goal, while following the above advice, is to find the maximum number of times you can buy the stock. You will be given the daily selling prices of a stock over a period of time, and you may choose on which days to buy. Every purchase must follow the “buy low; buy lower” principle. Write a program to compute the maximum number of purchases.

Here is a price list for a certain stock:

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \textsf{日期} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \cr\hline \textsf{价格} & 68 & 69 & 54 & 64 & 68 & 64 & 70 & 67 & 78 & 62& 98 & 87 \cr\hline \end{array}$$

The best investor can buy at most $4$ times. One feasible plan is:

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textsf{日期} & 2 & 5 & 6 & 10 \cr\hline \textsf{价格} & 69 & 68 & 64 & 62 \cr\hline \end{array}$$

Input Format

The first line contains a single integer $N\ (1 \le N \le 5000)$, the number of trading days.

The second line contains $N$ integers, the stock price for each day. Each is guaranteed to be a positive integer not exceeding $2^{16}$.

Output Format

Output two integers in one line: the maximum number of purchases, and the number of schemes that achieve this maximum (guaranteed $\le 2^{31}$). When two schemes “look the same” (that is, they form the same sequence of prices), the two schemes are considered identical.

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

4 2

Hint

Translated by ChatGPT 5