前缀最大值个数期望是 $\log n$ 的，时间复杂度 $q\log n$，空间 $n$。

#include <bits/stdc++.h>

using namespace std;

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

const int maxn = 2e7 + 10;
typedef unsigned long long ull;
int a[maxn];
int lst[maxn], ltop;
int rst[maxn], rtop;
int lm[maxn], rm[maxn];

signed main() {
	ull tot = 0;
	int n, q, s;
	cin >> n >> q >> s;
    srand(s);
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
	for (int i = 1; i <= n; ++i) {
        while (ltop && a[lst[ltop]] <= a[i]) --ltop;
        lm[i] = !ltop ? 0 : lst[ltop];
        lst[++ltop] = i;
    }
    for (int i = n; i >= 1; --i) {
        while (!rtop && a[rst[rtop]] <= a[i]) --rtop;
        rm[i] = !rtop ? n + 1 : rst[rtop];
        rst[++rtop] = i;
    }
	while (q--) {
		int l, r, p, q;
		l = read() % n + 1;
        r = read() % n + 1;
        if (l > r) swap(l, r);
		p = l, q = r;
		int ans = 0;
		while (p <= r && q >= l && p <= q) {
			ans = max(ans, max(a[p], a[q]));
			p = rm[p], q = lm[q];
		}
		tot += (ull) ans;
	}
	cout << tot << endl;
	return 0;
}