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

-----Examples-----
Sample Input 1:
7
2 3 1 5 4 7 6
Sample Output 1:
4
2 3 5 7

Sample Input 2:
5
1 2 3 4 5
Sample Output 2:
5
1 2 3 4 5

Source: kattis | Difficulty: EASY
Tags: Data structures


Solutions: