817D - Imbalanced Array - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define N 1000007
using namespace std;
int n, a[N], l[N], r[N];
ll ans;
inline int read(){
    int ans = 0, f = 1;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar())
		if (ch == '-')
		    f = 0;
	for(; ch >= '0' && ch <= '9'; ch = getchar())
	    ans = (ans << 3) + (ans << 1) + ch - 48;
	return f? ans: -ans;
}
int main(){
    n = read();
    ans = 0;
    for (int i = 1;i <= n; ++i)
	    a[i] = read();
    for (int i = 1; i <= n; ++i)
	    l[i] = r[i] = i;
    for (int i = 2; i <= n; ++i){
        int now = i;
        while (now > 1 && a[i] >= a[now - 1])
		    now = l[now - 1];
        l[i] = now;
    }
    for (int i = n - 1; i >= 1; --i){
        int now = i;
        while (now < n && a[i] > a[now + 1])
		    now = r[now + 1];
        r[i] = now;
    }
    for (int i = 1;i <= n; ++i)
	    ans += (ll)a[i] * (ll)(i - l[i] + 1) * (ll)(r[i] - i + 1);
    for (int i = 2; i <= n; ++i){
        int now = i;
        while (now > 1 && a[i] <= a[now - 1])
		    now = l[now - 1];
        l[i] = now;
    }
    for (int i = n - 1; i >= 1; --i){
        int now = i;
        while (now < n && a[i] < a[now + 1])
		    now = r[now + 1];
        r[i] = now;
    }
    for (int i = 1;i <= n; ++i)
	    ans -= (ll)a[i] * (ll)(i - l[i] + 1) * (ll)(r[i] - i + 1);
    printf("%lld\n", ans);
}