Shared code

// Then which of Allah's favor will you deny?
// author: MushfiqTalha
#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
using namespace std;
typedef long long LL;

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

  int n, q;
  cin >> n >> q;
  vector<LL> a(n);
  vector<tuple<int, int, int>> query(q);
  for (LL& e: a) cin >> e;
  for (int i = 0; i < q; i++) {
    auto &[l, r, k] = query[i];
    cin >> l >> r;
    l--, r--;
    k = i;
  }

  sort(all(query));

  // 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), ans(q);
  vector<int> stk{n};
  for (int i = n-1, j = q-1; ~i and ~q; i--) {
    suf[i] = suf[i+1] + a[i];
    while (stk.size() and a[stk.back()] <= a[i]) stk.pop_back();
    int p = stk.size() ? stk.back() : n;
    contrib[i] = contrib[p] + a[i]*(p-i);
    stk.push_back(i);

    while (~j and get<0>(query[j]) == i) {
      auto [l, r, k] = query[j--];

      // Finding out the maximum element's index less than r
      int m = *--upper_bound(stk.rbegin(), stk.rend(), r);

      // Add the sub-range contributions
      ans[k] = contrib[l] - contrib[m] + a[m] * (r-m+1);
      // subtracting range sum of [l,r]
      ans[k] -= suf[l] - suf[r+1];
    }
  }

  for (auto e: ans) cout << e << '\n';

  return 0;
}