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

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定正整数序列 x1∼xn x_1 \sim x_n x1xn,以下递增子序列均为非严格递增。

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

输入格式

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

输出格式

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

样例

样例输入

4
3 6 2 5

样例输出

2
2
3

数据范围与提示

1≤n≤500 1 \leq n \leq 500 1n500