9002: [yosupo] Other - Longest Increasing Subsequence
[Creator : ]
Description
You are given an integer sequence $A$ with the length $N$. Find a longest increasing subsequence of $A$.
Input
$N$
$A_0$ $A_1$ $\dots$ $A_{N - 1}$
$A_0$ $A_1$ $\dots$ $A_{N - 1}$
Output
On line $1$, output the maximum length $K$ of an increasing subsequence of $A$.
On line $2$, Print an increasing subsequence of length $K$.
$i_k$ is the index of the kth element of the subsequence.
$K$
$i_0$ $i_1$ $\dots$ $i_{K - 1}$
On line $2$, Print an increasing subsequence of length $K$.
$i_k$ is the index of the kth element of the subsequence.
$K$
$i_0$ $i_1$ $\dots$ $i_{K - 1}$
Constraints
$1 \leq N \leq 5 \times 10^5$
$0 \leq A_i \leq 10^9$
$0 \leq A_i \leq 10^9$
Sample 1 Input
5
3 1 4 1 5
Sample 1 Output
3
1 2 4
Sample 2 Input
5
3 3 2 3 1
Sample 2 Output
2
2 3