Районная олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача H. Возрастающие подмассивы

Вам дан массив $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$ строк - ответы на запросы.

Примеры

Вход

4 3
3 1 4 2
1 4
1 3
4 4

Выход

3
2
1