画一个平面，横轴是 $l$，纵轴是 $k$。

考虑一个点 $u$ 的贡献，找出其左边第一个比它小的 $pre_u$ 和右边第一个比它小的 $nxt_u$，那么贡献形如：

是斜距加，然后是求行区间和。

经典的，先把斜距差分成四个三角加：

然后三角加能拆成两个后缀加：

其中黄色的那个后缀加坐标系是斜的，所以点需要映射到 $(u+i,i)$。

对 $k$ 扫描线后需要支持区间加区间和，使用树状数组即可，时间复杂度 $O(n \log n)$。

const int N = 2e5 + 5;
int n, q, a[N];
int stk[N], tp;
int pre[N], nxt[N];
struct Query { int l, r, i; };
VC<Query> e[N];
VC<PII> f[N];
ll ans[N];
struct fenwick {
	ll c[N], d[N];
	inline int lowbit(int x) {
		return - x & x;
	}
	void add(int u, ll x) {
		for(int i = u; i <= n * 2; i += lowbit(i)) {
			c[i] += x;
			d[i] += x * (u - 1);
		}
	}
	ll query(int u) {
		ll res = 0;
		for(int i = u; i; i -= lowbit(i)) {
			res += c[i] * u;
			res -= d[i];
		}
		return res;
	}
	ll query(int l, int r) {
		return query(r) - query(l - 1);
	}
} t1, t2;
void solve() {
	read(n, q);
	FOR(i, 1, n) read(a[i]);
	tp = 0; stk[tp] = 0;
	FOR(i, 1, n) {
		while(tp && a[stk[tp]] >= a[i]) tp --;
		pre[i] = stk[tp];
		stk[++ tp] = i;
	}
	tp = 0; stk[tp] = n + 1;
	ROF(i, n, 1) {
		while(tp && a[stk[tp]] > a[i]) tp --;
		nxt[i] = stk[tp];
		stk[++ tp] = i;
	}
	FOR(i, 1, n) {
		f[1].eb(i, a[i]);
		f[i - pre[i] + 1].eb(pre[i], - a[i]);
		f[nxt[i] - i + 1].eb(i, - a[i]);
		f[nxt[i] - pre[i] + 1].eb(pre[i], a[i]);
	}
	FOR(i, 1, q) {
		INT(l, r, k);
		e[k].pb({l, r - k + 1, i});
	}
	FOR(i, 1, n) {
		for(auto [u, x] : f[i]) {
			if(u < 1) continue;
			t1.add(u + 1, - x);
			t2.add(u + i, x);
		}
		for(auto h : e[i]) {
			int l = h.l, r = h.r;
			ans[h.i] += t1.query(l, r);
			ans[h.i] += t2.query(l + i, r + i);
		}
	}
	FOR(i, 1, q) print(ans[i]);
}