Последовательность называется отсортированной, если она является неубывающей или невозрастающей. Например, последовательности [3, 1, 1, 0] и [1, 2, 3, 100] — отсортированы, но последовательность [1, 3, 3, 1] — нет. Вам дана последовательность чисел. Ваша задача — найти ее кратчайшую подпоследовательность, не являющуюся отсортированной.
Подпоследовательность — это последовательность, которая получается из данной путем удаления нуля или более ее элементов.
В первой строке записано целое число n (1 ≤ n ≤ 105). Далее через пробел записано n целых чисел, по модулю не превосходящих 106 — заданная последовательность чисел.
Если кратчайшей неотсортированной подпоследовательности не существует, выведите 0. Иначе выведите ее длину k, а затем k целых чисел от 1 до n включительно — индексы элементов последовательности, образующих кратчайшую неотсортированную подпоследовательность. Если решений несколько, выведите любое.
5
67 499 600 42 23
3
1 3 5
3
1 2 3
0
3
2 3 1
3
1 2 3
Название |
---|