问题描述

给定一个长度为 $n$ 的序列 $a$，你需要输出如下内容：

第一行输出该序列最长严格上升子序列的长度。

第二行输出该序列最少的严格上升子序列的划分个数。

第三行输出该序列最长非严格上升子序列的长度。

第四行输出该序列最少的非严格上升子序列的划分个数。

严格上升：对于 $i<j,a_i<a_j$。

非严格上升：对于 $i<j,a_i\le a_j$。

最少的严格上升子序列的划分个数：对于一个子序列，其最少可以划分成几个严格上升子序列。例如 $[3,1,2,2,3]$，我们最少可以划分成 $[3],[1,2],[2,3]$。

输入格式

第一行输入一个正整数 $n$。$(1\le n\le 1000)$

第二行输入 $n$ 个整数，表示序列 $a$。$(1\le a_i\le 100,1\le i\le n)$

输出格式

第一行输出该序列最长严格上升子序列的长度。

第二行输出该序列最少的严格上升子序列的划分个数。

第三行输出该序列最长非严格上升子序列的长度。

第四行输出该序列最少的非严格上升子序列的划分个数。

样例输入

10
1 4 7 3 6 8 1 3 4 4

样例输出

4
4
5
3

提示