题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，请求出它的最长上升子序列的长度，以及有多少个位置上的元素可能出现在最长上升子序列中，多少个位置上的元素一定出现在最长上升子序列中？

例如，给定序列 3,1,2,5,4中： {1,2,5}与{1,2,4}均为满足条件的最长上升子序列，该序列的最长上升子序列的长度为$3$。元素1,2,4,5 均有可能出现在最长上升子序列中，故有 $4$ 个位置上的元素可能出现在最长上升子序列中，而元素 1,2 必然出现在最长上升子序列中，故有 $2$ 个位置上的元素一定出现在最长上升子序列中。

输入格式

输入共两行： 输入第一行，一个整数 $n$，表示给定序列元素个数 输入第二行，$n$ 个正整数，分别表示 $a_1,a_2,\ldots,a_n$。

输出格式

输出共一行：第一行：输出三个数字，分别表示最长上升子序列长度，可能出现在最长上升子序列中的元素位置个数，及必然出现在最长上升子序列中元素位置个数，用空格隔开。

5
3 1 2 5 4

3 4 2

样例解释 1

样例说明请见题面

6
4 5 6 1 2 3

3 6 0

样例解释 2

最长上升子序列的长度为3 可能的最长上升子序列的有{4,5,6} 与 {1,2,3} 因此，有6个位置上的元素可能出现在最长上升子序列中，有0个位置上的元素一定出现在最长上升子序列中。

数据范围

• 对于 $30\%$ 的数据，$1\leq n \leq 10$；
• 对于 $70\%$ 的数据，$1\leq n \leq 10^4$；
• 对于 $100\%$ 的数据，$1\leq n \leq 10^5$；$1 \leq a_i \leq 10^9$