Hide

Problem D
Greedily Increasing Subsequence

Given a permutation $A = (a_1, a_2, \dots , a_ N)$ of the integers $1, 2, \dots , N$, we define the greedily increasing subsequence (GIS) in the following way.

Let $g_1 = a_1$. For every $i > 1$, let $g_ i$ be the leftmost integer in $A$ that is strictly larger than $g_{i-1}$. If there for a given $i$ is no such integer, we say that the GIS of the sequence is the sequence $(g_1, g_2, ..., g_{i - 1})$.

Your task is to, given a permutation $A$, compute the GIS of $A$.

Input

The first line of input contains an integer $1 \le N \le 10^6$, the number of elements of the permutation $A$. The next line contains $N$ distinct integers between $1$ and $N$, the elements $a_1, \dots , a_ N$ of the permutation $A$.

Output

First, output a line containing the length $l$ of the GIS of $A$. Then, output $l$ integers, containing (in order) the elements of the GIS.

Explanation of sample 1

In this case, we have the permutation $2, 3, 1, 5, 4, 7, 6$. First, we have $g_1 = 2$. The leftmost integer larger than $2$ is $3$, so $g_2 = 3$. The leftmost integer larger than $3$ is $5$ ($1$ is too small), so $g_3 = 5$. The leftmost integer larger than $5$ is $7$, so $g_4 = 7$. Finally, there is no integer larger than $7$. Thus, the GIS of $2, 3, 1, 5, 4, 7, 6$ is $2, 3, 5, 7$.

Sample Input 1 Sample Output 1
7
2 3 1 5 4 7 6
4
2 3 5 7
Sample Input 2 Sample Output 2
5
1 2 3 4 5
5
1 2 3 4 5
Sample Input 3 Sample Output 3
5
5 4 3 2 1
1
5

Please log in to submit a solution to this problem

Log in