Sunset

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 100001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);


using namespace std;

int n , q , val[SIZE] , h[SIZE];

stack<int>st;

vector<int>tree[4 * SIZE];

void build(int v,int l,int r) {
    if (l == r) {
        tree[v].push_back(val[l]);
        return;
    }
    int m = (l + r) >> 1;
    build(v << 1,l,m);
    build(v << 1 | 1,m + 1,r);
    merge(tree[v << 1].begin(),tree[v << 1].end(),tree[v << 1 | 1].begin(),tree[v << 1 | 1].end(),back_inserter(tree[v]));
}

int getans(int v,int l,int r,int le,int ri,int val) {
    if (l > ri || r < le)return 0;
    if (l >= le && r <= ri) {
        //cout<<l<<" "<<r<<" "<<val<<endl;
        //for (int i : tree[v])cout<<i<<" ";
        //cout<<endl;
        //cout<<lower_bound(tree[v].begin(),tree[v].end(),val) - tree[v].begin()<<endl;
        //cout<<endl;
        return lower_bound(tree[v].begin(),tree[v].end(),val) - tree[v].begin();
    }
    int m = (l + r) >> 1;
    return getans(v << 1,l,m,le,ri,val) + getans(v << 1 | 1,m + 1,r,le,ri,val);
}

int main()
{
    FAST_READ;
    cin>>n>>q;
    for (int i = 1;i<=n;i++) cin>>h[i];
    for (int i = 1;i<=n;i++) {
        while (st.empty() == false && h[st.top()] < h[i])st.pop();
        if (st.empty())val[i] = -1;
        else val[i] = st.top();
        st.push(i);
    }
    build(1,1,n);
    int l , r;
    while (q--) {
        cin>>l>>r;
        cout<<getans(1,1,n,l,r,l)<<endl;
    }
    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: ACCEPTED

Test 42

Group: 3

Verdict: ACCEPTED

Test 43

Group: 3

Verdict: ACCEPTED

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED