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$.

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$.

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.

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 |