最长递增子序列(LIS)问题是拆点的最大流方法：处理不相交路径的问题可用最大流

设有一组正整数序列 x_1,\cdots,x_n。

• 确定该序列中最长非严格递增子序列的长度 s。
• 探究在不重复使用原序列中任一元素的前提下，能够提取出多少个长度为 s 的非严格递增子序列。
• 若允许在所提取的子序列中重复使用 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