RT

#include <bits/stdc++.h> 
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)  
typedef long long ll;
typedef unsigned long long ull; 
using namespace std; 
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1) 

const int N = 1e5 + 5;
int n, Q;
int a[N];
int sta[N], h;

struct pos {
    int l, r, id;
}q[N];

struct node {
    ll sx, s;
}tr[N<<2];

struct tag {
    ll cx;
    ll ax, c;
    bool _emtpy () {return (!(cx || ax || c));}
    void clr () {cx = ax = c = 0;}
}tg[N<<2];

inline node merge (node a, node b) {
    b.sx += a.sx;
    b.s += a.s;
    return b;
}

inline node merge (node a, tag b, ll len) {
    a.s += a.sx * b.ax + len * b.c;
    if(b.cx) {
        a.sx = len * b.cx;
    } 
    return a;
}

inline tag merge (tag a, tag b) {
    if(b.cx) {
        b.c += a.ax * b.cx + a.c;
    }
    else {
        b.ax += a.ax;
        b.c += a.c;
    }
    if(a.cx) b.cx = a.cx;
    return b;
}

inline void pushup (int p, int l, int r) {
    tr[p] = merge(tr[ls(p)], tr[rs(p)]);
}

void pushdown (int p, int l, int r) {
    if(!tg[p]._emtpy()) { 
        int mid = (l + r) >> 1;
        tg[ls(p)] = merge(tg[p], tg[ls(p)]), 
        tg[rs(p)] = merge(tg[p], tg[rs(p)]);
        tr[ls(p)] = merge(tr[ls(p)], tg[p], mid - l + 1);
        tr[rs(p)] = merge(tr[rs(p)], tg[p], r - mid);
        tg[p].clr();
    }
}

ll query (int p, int l, int r, int dl, int dr) {
    if(dl <= l && r <= dr) {
        return tr[p].s;
    }
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if(dl <= mid) res += query(ls(p), l, mid, dl, dr);
    if(dr > mid) res += query(rs(p), mid + 1, r, dl, dr);
    return res;
}

void update (int p, int l, int r, int dl, int dr, tag t) {
    if(dl <= l && r <= dr) {
        tr[p] = merge(tr[p], t, r - l + 1);
        tg[p] = merge(t, tg[p]);
        return ;
    }
    pushdown(p, l, r); 
    int mid = (l + r) >> 1;
    if(dl <= mid) update(ls(p), l, mid, dl, dr, t);
    if(dr > mid) update(rs(p), mid + 1, r, dl, dr, t);
    pushup(p, l, r);
}

bool cmp (pos a, pos b) {
    return a.r < b.r;
}

ll ans[N];

int main () {
    scanf("%d %d", &n, &Q);
    int mn = 0x3f3f3f3f;
    re(i, n) scanf("%d", &a[i]), mn = min(mn, a[i]);
    re(i, n) a[i] = a[i] - mn + 1;
    re(i, Q) {
        scanf("%d %d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + Q + 1, cmp);
    int now = 1;
    re(i, n) {
        while(h && a[sta[h]] > a[i]) --h;
        update(1, 1, n, sta[h] + 1, i, (tag){a[i], 0, 0}); 
        sta[++h] = i;
        update(1, 1, n, 1, i, (tag){0, 1, 0});
        while(q[now].r < i) ++now;
        while(q[now].r == i) {
            ans[q[now].id] = query(1, 1, n, q[now].l, i);
            int len = i - q[now].l + 1;
            ans[q[now].id] += 1ll * (len + 1) * len / 2 * (mn - 1); 
            ++now;
        }
    }
    re(i, Q) printf("%lld\n", ans[i]);
    return 0;
}