• 从左往右考虑，对每一个 $a[i]$，找到最靠右的下标 $p[i]$，使得 $a[i], a[i + 1], \cdots, a[p[i]]$ 是稳定数组
• $p[i]$ 是 单调 的（思考下为什么？）
• 针对每个询问 $[l, r]$，分两种情况考虑
  • 如果下标 $i$ 的 $p[i] \le r$，这部分可以通过 前缀和 求出
  • 如果下标 $i$ 的 $p[i] > r$，这部分是一个 等差数列求和
  • 由于 $p[]$ 是 单调 的，以上两部分的分界点可以通过 二分查找 在 $O(log(n))$ 时间内确定

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

vector<i64> solve(vector<int>& a, vector<vector<int>>& q) {
    int n = a.size(), m = q.size();

    // p[i]: 表示最大的下标, 是的从 a[i] 到 a[p[i]] 是稳定子数组
    // p[] 数组肯定是单调不降的
    vector<int> p(n + 1);
    for (int i = 1, j = 1; i <= n; i++, j = max(j, i)) {
        while (j + 1 <= n && a[j] >= a[j - 1]) j++;
        p[i] = j;
    }

    // f[] 是 p[] 的前缀和
    vector<i64> f(n + 1, 0);
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] + p[i] - i + 1;

    vector<i64> ans(m, 0);
    for (int i = 0; i < m; i++) {
        int l = q[i][0] + 1, r = q[i][1] + 1;
        
        // 在 p[l ... r] 中找到第 1 个 >= r 的下标
        int x = lower_bound(p.begin() + l, p.begin() + r + 1, r) - p.begin();
        
        // p[l] + ... + p[x - 1]
        ans[i] = f[x - 1] - f[l - 1];

        // p[x], p[x + 1], ... p[r] 是一个等差数列
        i64 d = r - x + 1;
        ans[i] += (1 + d) * d / 2;
    }
    return ans;
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<vector<int>> q(m, vector<int>(2));
    for (int i = 0; i < m; i++) cin >> q[i][0] >> q[i][1];
    
    vector<i64> ans = solve(a, q);
    for (int i = 0; i < m; i++) cout << ans[i] << " \n"[i == m - 1];

    return 0;
}