题目描述

给定正整数序列$\red{x_1 ,... , x_n}$ 。

• （1）计算其最长递增子序列的长度$\red s$。（严格递增）
• （2）计算从给定的序列中最多可取出多少个长度为$\red s$的递增子序列。
• （3）如果允许在取出的序列中多次使用$\red{x_1}$和$\red{x_n}$，则从给定序列中最多可取出多少个长 度为$\red s$的递增子序列。

编程任务： 设计有效算法完成（1）（2）（3）提出的计算任务。

输入格式

文件第$\red 1$ 行有$\red 1$个正整数$\red {n(n<400)}$，表示给定序列的长度。

接 下来的$\red1$ 行有$\red n$个正整数 $\red {x_1 , ... , x_n}$。

输出格式

第$\red 1$ 行是最长 递增子序列的长度$\red s$。

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

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

样例

输入样例

4
3 6 2 5

输出样例

2
2
3