SecvCost infopro X

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("secvcost.in");
ofstream fout("secvcost.out");

int32_t main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int N, Q;
    fin >> N >> Q;
    vector < int > a(N + 2), lg(N + 2, 1);
    a[0] = a[N + 1] = INF;
    for(int i = 1; i <= N; ++i)
        fin >> a[i];
    for(int i = 1; i <= N; ++i) {
        int st = i - 1, dr = i + 1;
        while(a[st] < a[i])
            --st;
        while(a[dr] < a[i])
            ++dr;
        lg[i] += i - st - 1;
        lg[i] += dr - i - 1;
    }
    a[0] = 0;
    for(int i = 1; i <= N; ++i) {
        a[i] *= lg[i];
        a[i] += a[i - 1];
    }
    while(Q--) {
        int st, dr;
        fin >> st >> dr;
        fout << a[dr] - a[st - 1] << '\n';
    }
}