Supernumbers in a Permutation

Time limit1sMemory limit128 MB

Summary

Given a permutation, find every value that appears in some longest increasing subsequence, and print them in increasing order.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Sorting
Solved: No attempts yet

Problem

A permutation of $n$ elements is a sequence of length $n$ made up of distinct numbers from the set {1, 2, ..., $n$ }. For example, the sequence 2, 1, 4, 5, 3 is a permutation of 5 elements.

In this problem we care about the longest increasing subsequences of a permutation. In the example permutation above, the longest increasing subsequences have length 3, and there are exactly two of them: 2, 4, 5 and 1, 4, 5.

A supernumber is any number that belongs to at least one of the longest increasing subsequences. In the permutation 2, 1, 4, 5, 3 the supernumbers are 1, 2, 4, 5, while the number 3 is not a supernumber.

Your task is to find all supernumbers of a given permutation.

Write a program that:

reads a permutation from standard input,
finds all supernumbers,
prints the supernumbers to standard output.

Input

The input consists of two lines. The first line contains a single integer $n$ ( $1 \le n \le 100000$ ). The second line contains the $n$ integers of the permutation, separated by single spaces.

Output

The output consists of two lines. The first line contains $m$ , the number of supernumbers in the input permutation. The second line contains the supernumbers, in increasing order, separated by single spaces.

Examples1

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