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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Вам дан массив aa длины nn и qq запросов. В каждом запросе вам даются два числа l,r (1lrn)l, r \ (1 \leq l \leq r \leq n), нужно разбить подмассив al,al+1,,ara_l, a_{l+1}, \ldots, a_r на минимальное количество возрастающих подмассивов. Выведите это количество для каждого запроса.

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

Первая строка содержит два числа n,qn, q - размер массива и количество запросов. Во второй строке находятся nn чисел - массив a (1ai105)a \ (1 \leq a_i \leq 10^5). Следующие qq строк содержат два числа l,rl, r - описания запросов.

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

Выведите qq строк - ответы на запросы.

Примеры

Вход

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

Выход

3
2
1