题目描述

给定一个 $1\sim n$ 的排列 $p$，请从这里面取出尽可能多的不交的上升子序列，且他们的长度为原排列的 LIS 的长度，并构造一组方案。

输入格式

第一行为一个整数 $n$。

接下来一行 $n$ 个整数 $p_i$。

输出格式

第一行请输出您选择的上升子序列个数与他们的长度。

接下来若干行，一行若干个整数，表示某个上升子序列的每个元素的下标。

您可以以任意顺序输出您选择的上升子序列。

3
1 2 3

1 3
1 2 3

4
4 3 2 1

4 1
1
2
3
4

7
2 1 6 5 7 3 4

2 3
1 3 5
2 6 7

提示

数据范围

对于全部数据，$1\le n\le 10^6$，$1\le p_i\le n$。

说明

本题总分 $110$ 分。

本题译自 Croatian Open Competition in Informatics 2021/2022 Contest #1 T5 Volontiranje。

在附加文件中下发了一份 checker.cpp。