Nurlybek Aimagambetov

Есеп №1.

Есеп H. Өспелі бөліктер

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

1 second

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

256 megabytes

Сізде ұзындығы $n$ $a$ массивы бар. Берілген массивке байланысты сізге $q$ рет сұрақ қойылады. Сұрақтардың бәрінің үлгісі бірдей, тек сандары өзгереді. Әр сұрақта сізге белгілі бір аралықты анықтайтын $l$ және $r$ берілген. Осы аралықты ($a_l, a_{l+1}, \ldots, a_r$) $k$ бөлікке бөліңіз. Бірақ, әр бөлігін жеке алып қараған кезде тек өспелі массив шығу керек. $k$-ның мәнін барынша кішірейтіңіз.

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

Бірінші жолда екі сан берілген $n, q$ - массивтін ұзындығы және сұраулар саны. Екінші жолда $n$ сан берілген - а массиві. Әр келесі $q$ жолда екі сан берілген, $l$ және $r$.

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

Әр сұрақта берілген аралықты ережеге сәйкес $k$ рет бөліңіз және $k$-ның мәнін шығарыңыз.

Пример:

Вход

Ответ

3
2
1

Замечание

Егер барлық $l \leq i \leq r - 1$ үшін $a_i < a_{i+1}$ болса, $a_l, a_{l+1}, \ldots, a_r$ массив бөлігі өспелі деп аталады. Бірінші мысалдағы сұрауларға жауаптар: $ \\ $ [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) олимпиада