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