随机数据单调栈做法，70pts 求卡常。

前缀最大值个数期望是 \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;
}