题目描述

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

$\red{(1)}$计算其最长递增子序列的长度$\red{s.}$

$\red{(2)}$计算从给定的序列中最多可取出多少个长度为$\red{s}$的递增子序列。

$\red{(3)}$如果允许在取出的序列中多次使用$\red{x_1}$和$\red{x_n,}$则从给定序列中最多可取出多少个长 度为$\red{s}$的递增子序列。

注意任务$\red{(2)}$是取出。。。且题中递增是非严格递增

任务$\red{3}$若能取出无限的序列，则输出$\red{-1}$

设计有效算法完成$\red{(1) (2) (3)}$提出的计算任务。

输入格式

输入数据。文件第$\red{1}$行有$\red{1}$个正整数$\red{n,}$表示给定序列的长度。接 下来的$\red{1}$行有$\red{n}$个正整数$\red{x_1,...,x_n}$。

输出格式

程序运行结束时，将任务$\red{(1) (2) (3)}$的解答输出。

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

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

样例

输入样例1

4
1 3 2 4

输出样例1

3
1
2

输入样例2

4
3 6 2 5

输出样例2

2 
2
-1