P15748 [JAG 2024 Summer Camp #3] Halfway Through the Book

A book titled "Immense Catalog of Permutation Compilation" is published by JAG Publisher. This book is extremely lengthy, with a total of $2^N - 1$ pages. Each page contains one of the non-empty subsequences (not necessarily contiguous) of a permutation $\mathbf{P}$ of length $N$ (i.e., a rearrangement of $(1, \ldots, N)$). Each subsequence appears exactly once in lexicographical order. In other words, on the page $k$, you'll find the $k$-th lexicographically smallest subsequence of $\mathbf{P}$ among all non-empty subsequences. You've tried to read the entire book but gave up. However, you want to impress your friends by claiming that you read half of it, so you need to find the sequence on the exact middle page, which is page $2^{N-1}$. Your task is to determine this sequence.

The input consists of a single test case of the following format. $$\begin{aligned} & N \\ & P_1 \ P_2 \ \ldots \ P_N \end{aligned}$$ The first line contains an integer $N$, where $N$ represents the length of permutation $\mathbf{P}$. $N$ is between $1$ and $10,000$. The second line contains $N$ integers $P_1, \ldots, P_N$ ($1 \leq P_i \leq N$) which represent the permutation $\mathbf{P}$.

On the first line, print $M$, which represents the length of the sequence on page $2^{N-1}$. On the second line, print $M$ integers $Q_1, Q_2, \ldots, Q_M$, which represent the subsequence on page $2^{N-1}$.