乐师考核中的最长旋律

题目描述

在王城的音乐学院里，年轻乐师需要通过一场特别的考核。考官给出一段很长的音符记录，第 $i$ 个音符的音高记为一个整数 $a_i$。

乐师可以从这段记录中挑选若干个音符，按原来的先后顺序演奏，要求后面演奏的音符音高必须严格高于前面演奏的音符，即如果选择了若干位置 $i_1<i_2<\dots<i_k$，则需要满足

$$a_{i_1} < a_{i_2} < \dots < a_{i_k}.$$

为了展示自己的技巧，乐师希望这段演奏尽可能长。请你帮助他：

• 先计算在给定记录中，能挑出的最长长度是多少；
• 再给出任意一段满足条件的演奏音高序列。

输入格式

输入共两行。

• 第一行包含一个整数 $n$，表示音符的数量。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，依次表示每个音符的音高，整数之间用一个空格分隔。

输出格式

输出两行。

• 第一行输出一个整数，表示可以挑出的最长长度。
• 第二行输出一行若干整数，为其中一种满足要求的演奏音高序列，各整数之间用一个空格分隔。

如果存在多种不同的最优演奏方案，你可以输出任意一种。

输入输出样例 #1

输入 #1

6
2 1 5 3 6 4

输出 #1

3
2 5 6

（也可以输出 1 5 6、2 3 4 等任意一种满足要求的最优方案。）

数据范围

对于所有测试数据，保证：

• $1 \le n \le 200000$；
• 对于所有 $1 \le i \le n$，有 $1 \le a_i \le 10^9$。

保证至少存在一种合法的选择方案。