Sunset

/** MIT License Copyright (c) 2018-2019(!) Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
//code starts here
const int mod = 1e9 + 7;
const int N = 1e5 + 1;
int tree[N];
int lsb(int a) {return a & -a;}
int query(int r) { return r > 0 ? query(r - lsb(r)) + tree[r] : 0;}
void update(int p) { if (p < N) { tree[p]++; update(p + lsb(p));}}
void run() {
    memset(tree, 0, sizeof tree);
    int n, q;
    read(n, q);
    int h[n];
    rep(i, 0, n)
        get h[i];
    deque<int> mx, ind;
    int nearest[n];
    rep(i, 0, n) {
        while (!mx.empty() && mx.back() < h[i]) {
            mx.pop_back();
            ind.pop_back();
        }
        if (mx.empty())
            nearest[i] = -1;
        else
            nearest[i] = ind.back();
        mx.push_back(h[i]);
        ind.push_back(i);
    }

    vint queries[2 * q];
    int ans[q];
    memset(ans, 0, sizeof ans);
    rep(i, 0, q) {
        int l, r;
        read(l, r);
        queries[i << 1] = {r - 1, i + 1, l - 1};
        queries[i << 1 | 1] = {l - 2, -(i + 1), l - 1};
    }
    sort(queries, queries + 2 * q);
    int p = -1;
    int any = 0;
    for (vint i : queries) {
        while (p < i[0]) {
            p++;
            if (nearest[p] == -1)
                any++;
            else
                update(nearest[p] + 1);
        }
        if (i[1] < 0) {
            ans[-i[1] - 1] -= any + query(i[2]);
        } else
            ans[i[1] - 1] += any + query(i[2]);
    }
    rep(i, 0, q)
        put ans[i] << '\n';
}
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); 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