← 返回题目列表

Codeforces · 27/C

C. 无序子序列

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

如果序列是非递减或非递增的,则该序列称为有序序列。例如,序列 [3, 1, 1, 0] 和 [1, 2, 3, 100] 是有序的,但序列 [1, 3, 3, 1] 不是有序的。给你一个数字序列。你要找到它的最短的无序子序列。

子序列是可以通过删除零个或多个元素而不改变剩余元素的顺序从给定序列导出的序列。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105)。第二行包含 n 个空格分隔的整数——给定的序列。此序列中的所有数字的绝对值不超过 106。

输出

如果给定序列不包含任何无序子序列,则输出 0。否则,输出最短的此类子序列的长度 k。然后输出范围 [1..n] 中的 k 个整数——该子序列的元素的索引。如果有多个解,输出任意一个。

示例

输入 #1

5
67 499 600 42 23

输出 #1

3
1 3 5

输入 #2

3
1 2 3

输出 #2

0

输入 #3

3
2 3 1

输出 #3

3
1 2 3