Shared code

// Then which of Allah's favor will you deny?
// author: MushfiqTalha
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

/*            LCA template                */
struct LCA {
  const int n;
  vector<int> lvl, par, jmp;
  LCA(vector<vector<int>> const& g, int u, int p) : n(g.size()), lvl(n, -1), par(n, -1), jmp(n, -1) {
    lvl[u] = 0, par[u] = p;
    queue<int> q;
    for (q.push(u); q.size(); q.pop()) {
      int u = q.front();
      for (int v: g[u]) if (lvl[v] < 0) {
        q.push(v);
        lvl[v] = lvl[u] + 1, par[v] = u;
        if (lvl[jmp[u]] << 1 == lvl[u] + lvl[jmp[jmp[u]]])
          jmp[v] = jmp[jmp[u]];
        else
          jmp[v] = u;
      }
    }
  }
  int getR(int l, int r) {
    while (par[l] <= r)
      l = jmp[l] > r ? par[l] : jmp[l]; 
    return l;
  }
};

int main() {
  cin.tie(NULL)->sync_with_stdio(false);

  int n, q;
  cin >> n >> q;
  vector<LL> a(n);
  for (LL& e: a) cin >> e;

  // suf[i]     : suffix sum of range [i, n)
  // contrib[i] : contribution of sub-range [i, nextGreater(i)) added with
  //              the contrib[nextGreater(i)]
  //                - This array is the suffix sum of contributions of sub-ranges
  vector<LL> suf(n+1), contrib(n+1);
  vector<vector<int>> g(n+1);
  stack<int> s;
  for (int i = n-1; ~i; i--) {
    suf[i] = suf[i+1] + a[i];
    while (s.size() and a[s.top()] <= a[i]) s.pop();
    int p = s.size() ? s.top() : n;
    g[p].push_back(i);
    contrib[i] = contrib[p] + a[i]*(p-i);
    s.push(i);
  }

  // Pre-calculating the jumps
  LCA lca(g, n, n);

  for (int l, r; q--;) {
    cin >> l >> r;
    l--, r--;

    /* Finding sum of maximums of prefixes in [l,r] range */
    int m = lca.getR(l, r); // Finding the last sub-range's starting position
    LL ans = contrib[l] - contrib[m]; // Calculating contribution of sub-ranges w/o the last one
    ans += a[m]*(r-m+1); // Adding the contribution of the last sub-range

    /* Now, subtract the range sum of [l,r] from the answer */
    cout << ans - suf[l] + suf[r+1] << '\n';
  }

  return 0;
}