1161: #6005. 「网络流 24 题」最长递增子序列

给定正整数序列 x1∼xn x_1 \sim x_n x​1​​∼x​n​​，以下递增子序列均为非严格递增。

1. 计算其最长递增子序列的长度 $s$。
2. 计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。
3. 如果允许在取出的序列中多次使用 x1 x_1 x​1​​ 和 xn x_n x​n​​，则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。

输入格式

文件第 $1$ 行有 $1$ 个正整数 $n$，表示给定序列的长度。接下来的 $1$ 行有 $n$ 个正整数 x1∼xn x_1 \sim x_n x​1​​∼x​n​​。

输出格式

第 $1$ 行是最长递增子序列的长度 $s$。第 $2$ 行是可取出的长度为 $s$ 的递增子序列个数。第 $3$ 行是允许在取出的序列中多次使用 x1 x_1 x​1​​ 和 xn x_n x​n​​ 时可取出的长度为 $s$ 的递增子序列个数。

样例

样例输入

4
3 6 2 5

样例输出

2
2
3

数据范围与提示

$1\le n\le 500$