最长不下降子序列问题

题目描述

给定正整数序列 $x_1 \ldots, x_n$。 1. 计算其最长不下降子序列的长度 $s$。 2. 如果每个元素只允许使用一次,计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。 3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$(其他元素仍然只允许使用一次),则从给定序列中最多可取出多少个**不同的**长度为 $s$ 的不下降子序列。 令 $a_1, a_2, \ldots, a_s$ 为构造 $S$ 时所使用的下标,$b_1, b_2, \ldots, b_s$ 为构造 $T$ 时所使用的下标。且 $\forall i \in [1,s-1]$,都有 $a_i < a_{i+1}$,$b_i < b_{i+1}$。则 $S$ 和 $T$ **不同**,当且仅当 $\exists i \in [1,s]$,使得 $a_i \neq b_i$。

输入输出格式

输入格式


第一行有一个正整数 $n$,表示给定序列的长度。接下来的一行有 $n$ 个正整数$x_1, ..., x_n$。

输出格式


- 第 1 行是最长不下降子序列的长度 $s$。 - 第 2 行是可取出的长度为 $s$ 的不下降子序列个数。 - 第 3 行是允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 $s$ 的**不同的**不下降子序列个数。

输入输出样例

输入样例 #1

4
3 6 2 5

输出样例 #1

2
2
3

说明

$1 \le n\le 500$