Nurlybek Aimagambetov

Задача №1.

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вам дан массив

$a$ длины

$n$ и

$q$ запросов. В каждом запросе вам даются два числа

$l, r \ (1 \leq l \leq r \leq n)$ , нужно разбить подмассив

$a_l, a_{l+1}, \ldots, a_r$ на минимальное количество возрастающих подмассивов. Выведите это количество для каждого запроса.

Формат входного файла

Первая строка содержит два числа

$n, q$ - размер массива и количество запросов. Во второй строке находятся

$n$ чисел - массив

$a \ (1 \leq a_i \leq 10^5)$ . Следующие

$q$ строк содержат два числа

$l, r$ - описания запросов.

Формат выходного файла

Выведите

$q$ строк - ответы на запросы.

Пример:

Вход

Ответ

3
2
1

Замечание

Подмассив

$a_l, a_{l+1}, \ldots, a_r$ является возрастающим если для всех

$l \leq i \leq r - 1$ выполняется условие

$a_i < a_{i+1}$ .

$\\ \\$ Ответы на запросы в первом примере:

$\\$ [3, 1, 4, 2] - [3], [1, 4], [2]

$\\$ [3, 1, 4] - [3], [1, 4]

$\\$ [4] - [4]

$\\$ Подзадачи:

$\\ 1 \leq n, q \leq 1000 - 40 \ баллов. \\ 1 \leq n, q \leq 10^5 - 60 \ баллов. \\$ ( Nurlybek Aimagambetov )
комментарий/решение(3) олимпиада