A. Почти возрастающая подпоследовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность называется почти возрастающей, если она не содержит трех идущих подряд элементов $$$x, y, z$$$ таких, что $$$x\ge y\ge z$$$.

Вам дан массив $$$a_1, a_2, \dots, a_n$$$ и $$$q$$$ запросов.

Каждый запрос состоит из двух целых чисел $$$1\le l\le r\le n$$$. Для каждого запроса найдите длину самой длинной почти возрастающей подпоследовательности подмассива $$$a_l, a_{l+1}, \dots, a_r$$$.

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

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

Первая строка ввода содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$) — длину массива $$$a$$$ и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)  — значения массива $$$a$$$.

Каждая из следующих $$$q$$$ строк содержит описание запроса. Каждая строка содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — запрос, относящийся к подмассиву $$$a_l, a_{l+1}, \dots, a_r$$$.

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

Для каждого из $$$q$$$ запросов выведите строку, содержащую длину самой длинной почти возрастающей подпоследовательности подмассива $$$a_l, a_{l+1}, \dots, a_r$$$.

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

В первом запросе подмассив состоит из элементов $$$a_1, a_2, a_3 = [1,2,4]$$$. Весь подмассив является почти возрастающим, поэтому ответ равен $$$3$$$.

Во втором запросе подмассив состоит из элементов $$$a_1, a_2, a_3,a_4 = [1,2,4,3]$$$. Весь подмассив является почти возрастающим, потому что нет трех подряд идущих элементов таких, что $$$x \geq y \geq z$$$. Таким образом, ответ равен $$$4$$$.

В третьем запросе подмассив состоит из элементов $$$a_2, a_3, a_4, a_5 = [2, 4, 3, 3]$$$. Весь подмассив не является почти возрастающим, потому что последние три элемента удовлетворяют условию $$$4 \geq 3 \geq 3$$$. Почти возрастающую подпоследовательность длиной $$$3$$$ можно найти (например, взяв элементы $$$a_2,a_3,a_5 = [2,4,3]$$$). Таким образом, ответ равен $$$3$$$.