最长递增子序列

题目来源

网络流 24 题

题目描述

给定正整数序列 $x_1 \sim x_n$，以下递增子序列均为非严格递增。

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

输入格式

第一行有一个正整数 $n (1\leq n\leq 500)$，表示给定序列的长度。接下来的一行有 $n$ 个正整数 $x_1, x_2, \dots, x_n$。

输出格式

三行三个整数，分别表示上一问的答案。

样例输入

4
3 6 2 5

样例输出

2
2
3