Longest Non-Decreasing Subsequence Count

A farm has a fence consisting of n wooden posts numbered in order (the fence is not circular). Each post has a certain height. The task is to select some posts from the fence while preserving their original order such that the heights of the chosen posts form a non-decreasing sequence. In other words, if the selected posts have heights \(a_1, a_2, \dots, a_t\), then they must satisfy \(a_1 \leq a_2 \leq \dots \leq a_t\).

Your goal is to choose the posts so that the number of selected posts \(t\) is maximized. In addition, you need to compute the total number \(c\) of different ways to select \(t\) posts.

Input Constraint: The value of n (number of posts) is given, followed by n integers representing the heights of the posts.

Note: All formulas are provided in \(\LaTeX\) format. For example, the non-decreasing condition is \(a_1 \leq a_2 \leq \dots \leq a_t\).

inputFormat

The first line contains an integer n representing the number of wooden posts.

The second line contains n space-separated integers representing the heights of the posts.

outputFormat

Output two integers separated by a space: t, the maximum number of posts that can be selected, and c, the total number of ways to select these t posts.

sample

5
1 2 3 4 5

5 1