题目描述

给定正整数序列 $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 \lt a_{i+1}$，$b_i \lt 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$ 的不同的不下降子序列个数。

4
3 6 2 5

2
2
3

提示

$1 \le n\le 500$