1818C - Almost Increasing Subsequence - CodeForces Solution

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 2e5 + 10;
int v[MAXN], marc[MAXN], psum[MAXN];
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,q; cin >> n >> q;

    for(int i = 0; i <= n; i++) marc[i] = 1;

    int left = -1;
    int right = -1;
    v[0] = 0;
    v[n+1] = INF;
    for(int i = 1; i <= n; i++) cin >> v[i];

    for(int i = 1; i <= n; i++) if(v[i-1] >= v[i] && v[i] >= v[i+1]) marc[i] = 0;

    psum[0] = 0;
    for(int i = 1; i <= n; i++) {psum[i] = marc[i] + psum[i-1];}

    // cerr << "\n\n";

    // cerr << "\n\n";

    for(int i = 0; i < q; i++)
    {
        int l,r; cin >> l >> r;

        int resp = psum[r] - psum[l - 1];

        // cerr << psum[r] << " " << psum[l - 1] << "||\n";



        if(marc[l] == 0) resp++;
        if(marc[r] == 0) resp++;
        if(l == r && marc[l] == 0) resp--;
        cout << resp << "\n";
    }

}