最长递增子序列（Longest Increasing Subsequence）

问题描述

给定一个长度为 $N$ 的整数序列 $A$，求其最长递增子序列（LIS）——即一个下标严格递增、值也严格递增的子序列，且长度最大。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq A_i \leq 10^9$

输入

$N$
$A_0\ A_1\ \cdots\ A_{N-1}$

输出

$K$
$i_0\ i_1\ \cdots\ i_{K-1}$

其中：

• $K$ 是 LIS 的长度；
• $i_k$ 是所选子序列中第 $k$ 个元素在原序列中的下标（0-based），满足 $i_0 < i_1 < \cdots < i_{K-1}$ 且 $A_{i_0} < A_{i_1} < \cdots < A_{i_{K-1}}$。

5
3 1 4 1 5

3
1 2 4

5
3 3 2 3 1

2
2 3