Для данной последовательности целых чисел \(a\) длины \(n\) тройка \((i,j,k)\) называется монотонной, если
- \(1 \le i<j<k\le n\);
- \(a_i \le a_j \le a_k\) или \(a_i \ge a_j \ge a_k\) выполняется.
Например, \(a=[5,3,4,5]\), тогда \((2,3,4)\) — это монотонная тройка для последовательности \(a\), а \((1,3,4)\) нет.
Бобу на экзамене по математике дали последовательность целых чисел \(a\) длины \(n\). Сам же экзамен представляет собой вопросы вида \(L, R\), на каждый из которых его просят найти любую подпоследовательность \(b\) размера больше, чем \(2\) (то есть \(|b| \ge 3\)) последовательности \(a_L, a_{L+1},\ldots, a_{R}\).
Напомним, что последовательность \(b\) является подпоследовательностью \(a\), если \(b\) может быть получена удалением нескольких (возможно, ни одного или всех) элементов.
Однако, он ненавидит монотонные штуки, поэтому он хочет выбрать подпоследовательность без монотонных троек. Кроме того, он хочет выбрать подпоследовательность с наибольшей длиной среди всех подпоследовательностей без монотонных троек для каждого запроса.
Помогите Бобу найти подпоследовательность, удовлетворяющую приведенным условиям.
Выходные данные
Для каждого запроса выведите \(0\), если не существует подпоследовательности \(b\), удовлетворяющей всем условиям из легенды. Можно вывести пустую строку после этого, но это не обязательно.
В противном случае выведите одно целое число \(k\) (\(k > 2\)), обозначающее длину последовательности \(b\), затем выведите \(k\) целых чисел \(i_1, i_2, \ldots, i_k\) (\(L \le i_1 < i_2<\ldots<i_k\le R\)), где \(b_j = a_{i_j}\) для \(1 \le j \le k\).
Если существует несколько ответов с наибольшей длиной, то выведите любой из них.
Примечание
В первом примере в самой последовательности уже нет монотонных троек.
Во втором примере можно показать, что не существует подпоследовательности \(b\) длиной больше, чем \(2\), такой, что в \(b\) нет монотонных троек.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
3 1 4 1 5 9
1 3
4 6
|
3
1 2 3
0
|