[ABC354] F - Useless for LIS

F - Useless for LIS

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 525 分

题面

给定一个长度为 的整数序列 。

对于每个 ，确定 是否包含在 的最长递增子序列中。

这里， 包含在 的最长递增子序列中当且仅当满足以下条件：

• 设 为 的最长递增子序列的长度。存在一个严格递增的整数序列 ，其中每个元素都介于 和 之间（包括边界），满足以下所有条件：

  • 。
  • 存在某个 ，使得 。

给定 个测试用例；解决每个测试用例。

什么是最长递增子序列？

一个序列 的子序列是从 中提取一些元素而不改变其顺序得到的序列。

一个序列 的最长递增子序列是一个严格递增的子序列，其长度最大。

限制条件

• 所有测试用例中 的总和不超过 。

---

输入

输入从标准输入给出，格式如下：

这里， 表示第 个用例的输入。每个用例的格式如下：

输出

以以下格式打印答案：

这里， 表示第 个用例的输出。对于每个用例，设存在 个指数 ，使得 包含在 的最长递增子序列中，则这些指数为 ，按升序打印如下：

---

输入样例 1

1
5
2 1 4 5 3

输出样例 1

4
1 2 3 4

其中最长递增子序列之一为 ，长度为 。另一个最长递增子序列为 。然而，没有一个最长递增子序列包含 。

因此，打印 。

---

输入样例 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

输出样例 2

5
1 3 4 5 6
2
4 5