题目描述

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

输入描述:

输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr。

输出描述:

输出一行。代表你求出的最长的递增子序列。

样例1

输入

9
2 1 5 3 6 4 8 9 7

输出

1 3 4 8 9

样例2

输入

5
1 2 8 6 4

输出

1 2 4

说明

​ 其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）

​