#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;

const int maxn = 1e6 + 10;

#define int long long

int n, m;
int a[maxn];
int idx[maxn][2];
int ans[maxn];

int blo[maxn], siz;
struct query {
    int l, r;
    int id;
} q[maxn];
struct node {
    int val, pos;
} b[maxn];

int res, cnt[maxn];
void add(int x, int l, int r)
{
    res += cnt[x];
    cnt[idx[x][0]]++;
    cnt[idx[x][1]]++;
    if (idx[x][0] >= l && idx[x][0] <= r)
        res++;
    if (idx[x][1] >= l && idx[x][1] <= r)
        res++;
}
void del(int x, int l, int r)
{
    cnt[idx[x][0]]--;
    cnt[idx[x][1]]--;
    if (idx[x][0] >= l && idx[x][0] <= r)
        res--;
    if (idx[x][1] >= l && idx[x][1] <= r)
        res--;
    res -= cnt[x];
}

signed main()
{
    std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i].val = a[i], b[i].pos = i;
    sort(b + 1, b + n + 1, [](const node& x, const node& y) {
        return x.val < y.val;
    });
    b[0].pos = 0, b[n + 1].pos = n + 1;
    for (int i = 1; i <= n; i++) {
        idx[b[i].pos][0] = b[i - 1].pos,
        idx[b[i].pos][1] = b[i + 1].pos;
        if (b[i].val - b[i - 1].val > b[i + 1].val - b[i].val && b[i + 1].pos <= n)
            idx[b[i].pos][0] = 0;
        if (b[i].val - b[i - 1].val < b[i + 1].val - b[i].val && b[i - 1].pos)
            idx[b[i].pos][1] = n + 1;
    }
    // for (int i = 1; i <= n; i++)
    // cout << idx[i][0] << " " << idx[i][1] << "\n";
    siz = sqrt(n);
    for (int i = 1; i <= m; i++)
        cin >> q[i].l >> q[i].r, q[i].id = i, blo[i] = (i - 1) / siz + 1;
    sort(q + 1, q + m + 1, [](const query& x, const query& y) {
        if (blo[x.l] != blo[y.l])
            return x.l < y.l;
        return (blo[x.l] & 1 ? x.r < y.r : x.r > y.r);
    });
    int sum = 0;
    for (int i = 1, l = q[1].l, r = q[1].l - 1; i <= m; i++) {
        int ql = q[i].l, qr = q[i].r;
        while (l < ql)
            del(l, l, r), l++;
        while (l > ql)
            --l, add(l, l, r);
        while (r < qr)
            ++r, add(r, l, r);
        while (r > qr)
            del(r, l, r), r--;
        // cout << res << "\n";
        sum += res * q[i].id;
    }
    cout << sum << "\n";
    return 0;
}

雖然都是 wa，但是爲什麽 wa 的地方不一樣？