← 返回题目列表

Codeforces · 977/F

F. 连续子序列

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的整数数组。

您必须选择该数组的某个最大长度的子序列,使得该子序列形成连续整数的递增序列。换句话说,对于某个值 $$$x$$$ 和长度 $$$k$$$,所需的序列应等于 $$$[x, x + 1, \dots, x + k - 1]$$$。

数组的子序列可以通过从数组中删除一些(可能是零)元素来获得。您可以删除任何元素,不一定要连续删除。其余元素保留其顺序。例如,对于数组 $$$[5, 3, 1, 2, 4]$$$,以下数组是子序列:$$$[3]$$$、$$$[5, 3, 1, 2, 4]$$$、$$$[5, 1, 4]$$$,但数组 $$$[1, 3]$$$ 不是。

输入

输入的第一行包含整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组本身。

输出

在第一行打印 $$$k$$$ — 给定数组的子序列的最大长度,该子序列形成连续整数的递增序列。

在第二行打印给定数组的任何最大长度子序列的索引序列,该子序列形成连续整数的递增序列。

示例

输入 #1

7
3 3 4 7 5 6 8

输出 #1

4
2 3 5 6

输入 #2

6
1 3 5 2 4 6

输出 #2

2
1 4

输入 #3

4
10 9 8 7

输出 #3

1
1

输入#4

9
6 7 8 3 4 5 9 10 11

输出#4

6
1 2 3 7 8 9

注意

第一个示例的所有有效答案(作为索引序列):

- $$$[1, 3, 5, 6]$$$
- $$$[2, 3, 5, 6]$$$

第二个示例的所有有效答案:

- $$$[1, 4]$$$
- $$$[2, 5]$$$
- $$$[3, 6]$$$

第三个示例的所有有效答案:

- $$$[1]$$$
- $$$[2]$$$
- $$$[3]$$$
- $$$[4]$$$

第四个示例的所有有效答案:

- $$$[1, 2, 3, 7, 8, 9]$$$