Последовательность называется почти возрастающей, если она не содержит трех идущих подряд элементов \(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\).
Подпоследовательность — это последовательность, которая может быть получена из данной последовательности путем удаления нуля или более элементов без изменения порядка оставшихся элементов.
Выходные данные
Для каждого из \(q\) запросов выведите строку, содержащую длину самой длинной почти возрастающей подпоследовательности подмассива \(a_l, a_{l+1}, \dots, a_r\).
Примечание
В первом запросе подмассив состоит из элементов \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|