Description

Given a sequence of positive integers $x_1 \ldots, x_n$.

1. Compute the length $s$ of its longest non-decreasing subsequence.
2. If each element is allowed to be used at most once, compute the maximum number of non-decreasing subsequences of length $s$ that can be extracted from the given sequence.
3. If, in the extracted subsequences, $x_1$ and $x_n$ are allowed to be used multiple times (all other elements are still allowed to be used at most once), compute the maximum number of different non-decreasing subsequences of length $s$ that can be extracted from the given sequence.

Let $a_1, a_2, \ldots, a_s$ be the indices used to construct $S$, and $b_1, b_2, \ldots, b_s$ be the indices used to construct $T$. For all $i \in [1,s-1]$, we have $a_i \lt a_{i+1}$ and $b_i \lt b_{i+1}$. Then $S$ and $T$ are different if and only if there exists $i \in [1,s]$ such that $a_i \neq b_i$.

Input Format

The first line contains a positive integer $n$, which is the length of the given sequence. The following lines contain $n$ positive integers $x_1, ..., x_n$.

Output Format

• The first line is the length $s$ of the longest non-decreasing subsequence.
• The second line is the maximum number of non-decreasing subsequences of length $s$ that can be extracted.
• The third line is the maximum number of different non-decreasing subsequences of length $s$ that can be extracted when $x_1$ and $x_n$ are allowed to be used multiple times in the extracted subsequences.

4
3 6 2 5

2
2
3

Hint

Constraints: $1 \le n \le 500$.

Translated by ChatGPT 5