以下的代码：

#include<algorithm>
#include<iostream>
int n; const int mod = 1e9, N = 5e5 + 10;
long long a[N], rs, f[N], F[N], g[N], G[N], o[N], O[N];
inline void sol(int l, int r){
    if(l == r) return void((rs += a[l] * a[l]) %= mod);
    int mid = l + r >> 1; sol(l, mid); sol(mid + 1, r);
    long long mn = a[mid], mx = a[mid], 
    Mn = a[mid + 1], Mx = a[mid] + 1, p = mid, lp = p, rp = p;
    f[mid] = g[mid] = o[mid] = F[mid] = G[mid] = O[mid] = 0;
    for(int i = mid + 1; i <= r; i++){
        Mn = std::min(Mn, a[i]), Mx = std::max(Mx, a[i]);
        f[i] = (f[i - 1] + Mn * (i - mid) % mod) % mod, F[i] = (F[i - 1] + Mn) % mod;
        g[i] = (g[i - 1] + Mx * (i - mid) % mod) % mod, G[i] = (G[i - 1] + Mx) % mod;
        o[i] = (o[i - 1] + Mx * Mn % mod * (i - mid) % mod) % mod;
        O[i] = (O[i - 1] + Mx * Mn % mod) % mod;
    }
    while(p >= l){
        mn = std::min(mn, a[p]), mx = std::max(mx, a[p]);
        while(lp < r && a[lp + 1] > mn) lp++;
        while(rp < r && a[rp + 1] < mx) rp++;
        int pl = std::min(lp, rp), pr = std::max(lp, rp);
        if(pl > mid) (rs += mn * mx % mod * 
            ((mid + 3 - 2 * p + pl) *(pl - mid) / 2 % mod)% mod) %= mod;
        if(lp > pl) (rs += mn * ((g[lp] - g[pl] + mod) % mod + 
            (mid - p + 1) * (G[lp] - G[pl] + mod) % mod) % mod) %= mod;
        if(rp > pl) (rs += mx * ((f[rp] - f[pl] + mod) % mod + 
            (mid - p + 1) * (F[rp] - F[pl] + mod) % mod) % mod) %= mod;
        (rs += ((o[r] - o[pr] + mod) % mod + (mid - p + 1) * 
            (O[r] - O[pr] + mod) % mod) % mod) %= mod; p--;
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    std::cin >> n;
    for(int i = 1; i <= n; i++) std::cin >> a[i];
    sol(1, n); std::cout << rs;
}

在跑样例的时候结果是 116。然而 ???