G. Без монотонных троек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для данной последовательности целых чисел $$$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$$$ может быть получена удалением нескольких (возможно, ни одного или всех) элементов.

Однако, он ненавидит монотонные штуки, поэтому он хочет выбрать подпоследовательность без монотонных троек. Кроме того, он хочет выбрать подпоследовательность с наибольшей длиной среди всех подпоследовательностей без монотонных троек для каждого запроса.

Помогите Бобу найти подпоследовательность, удовлетворяющую приведенным условиям.

Входные данные

В первой строке записаны два числа $$$n$$$, $$$q$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — длина последовательности $$$a$$$ и количество запросов.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — последовательность $$$a$$$.

Затем в каждой из следующих $$$q$$$ строк записаны по два целых числа $$$L$$$, $$$R$$$ ($$$1 \le L,R \le n$$$, $$$R-L\ge 2$$$).

Выходные данные

Для каждого запроса выведите $$$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$$$.

Если существует несколько ответов с наибольшей длиной, то выведите любой из них.

Пример
Входные данные
6 2
3 1 4 1 5 9
1 3
4 6
Выходные данные
3
1 2 3 
0
Примечание

В первом примере в самой последовательности уже нет монотонных троек.

Во втором примере можно показать, что не существует подпоследовательности $$$b$$$ длиной больше, чем $$$2$$$, такой, что в $$$b$$$ нет монотонных троек.