2180

2180. 最长递增子序列问题

题目

给定正整数序列 $x_1,\cdots,x_n$。

1. 计算其最长递增子序列的长度 $s$。
2. 计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。（给定序列中的每个元素最多只能被取出使用一次）
3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$，则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。

注意:递增指非严格递增。

输入格式

第 $1$ 行有 $1$ 个正整数 $n$，表示给定序列的长度。

接下来的 $1$ 行有 $n$ 个正整数 $x_1,\cdots,x_n$。

输出格式

第 $1$ 行输出最长递增子序列的长度 $s$。

第 $2$ 行输出可取出的长度为 $s$ 的递增子序列个数。

第 $3$ 行输出允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 $s$ 的递增子序列个数。

数据范围

$1 \le n \le 500$

输入样例：

4
3 6 2 5

输出样例：

2
2
3

题解