Question

Новый маршрут для трекинга

Сейчас самое время планировать новые трекинговые маршруты.


Опишем холмистую местность массивом из n чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршрут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору — переходить с более низкого холма на более высокий.


Помогите туристам определиться с выбором маршрута — напишите программу, которая отвечает на запросы о количестве переходов с более низкого холма на более высокий на данном маршруте.


Входные данные


В первой строке даны натуральные числа n, m (2≤n,m≤2⋅105) — общее количество холмов и количество запросов соответственно.


Во второй строке даны n целых чисел hi(1≤hi≤105) — высоты холмов.


В следующих m строках записаны пары чисел lj и rj (1≤li≤rj≤n) — запросы на количество переходов с более низкого холма на более высокий на маршруте с началом в холме lj и завершением в rj.


Выходные данные


Выведите m чисел — ответы на запросы.


Примеры

Ввод

2 3

2 37

1 2

2 2

1 1

Вывод

1

0

0

Решить на C++

Answer 1

Ответ:

лол вроде же несложная задачка

Объяснение:

#include <bits/stdc++.h>

using namespace std;

int main () {

   int n,m;

   cin >> n >> m;

   vector <int> a(n), p(n, 0);

   for (int i = 0; i < n; i++)

       cin >> a[i];

   if (a[0] < a[1]) p[1] = 1;

   for (int i = 2; i < n; i++) {

       if (a[i - 1] < a[i]) p[i] = 1;

       p[i] += p[i-1];

   }

   for (int i = 0; i < m; i++) {

       int l, r;

       cin >> l >> r;

       cout << p[r - 1] - p[l - 1] << endl;

   }

}