Page not loading? Try clicking here.
Placeholder

#8714

Greedily Increasing Subsequence 1s 512MB

Problems

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.


Example #1

7
2 3 1 5 4 7 6
4
2 3 5 7

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.


Example #2

5
1 2 3 4 5
5
1 2 3 4 5

Example #3

5
5 4 3 2 1
1
5


Source

HiQ Challenge 2017 B번
You must sign in to write code.