Greedily Increasing Subsequence

Interview

Time limit1sMemory limit512 MB

Summary

Given a permutation, repeatedly take the leftmost unused element larger than the previous pick, and report the resulting subsequence.

Level: Medium4 of 10
Topics: Array, Simulation, Greedy, Implementation
Solved: No attempts yet

Problem

Given a permutation $A = (a_1, a_2, \dots, a_N)$ of the integers $1, 2, \dots, N$ , the greedily increasing subsequence (GIS) is defined as follows.

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 no such integer exists for some $i$ , the GIS of the sequence is $(g_1, g_2, \dots, g_{i-1})$ .

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, the elements of the GIS in order.

Examples3

Example 1
Input
```
7
2 3 1 5 4 7 6
```
Expected output
```
4
2 3 5 7
```
Example 2
Input
```
5
1 2 3 4 5
```
Expected output
```
5
1 2 3 4 5
```
Example 3
Input
```
5
5 4 3 2 1
```
Expected output
```
1
5
```