最长上升子序列(LIS Positions)

题目描述

给定一个长度为 $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$。

输出格式

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

样例输入 #1

5
3 1 2 5 4

样例输出 #1

3 4 2

样例输入 #2

6
4 5 6 1 2 3

样例输出 #2

3 6 0

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 7级（动态规划、二分查找、复杂DP），难度等级：⭐⭐⭐⭐。

测试点分布