Solution for educational contest 22, problem D. There you can find all the implementations next/prev x Greater/Smaller

cf_817D.cpp

// The problem is to find sum_i sum_j {max(segment[i,j]) - min(segment[i,j]}
// The main observation is that sum(i,j) of max - min = sum(i,j) max - sum(i,j) min
// To find sum of all the maximums we find how many time each number might be maximum by using standard 
// technique of looking forward/backward
// https://codeforces.com/contest/817/problem/D
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

// For a given index i, finds and saves index of 
// the first greater element on the right side.
// If it doesn't exist, -1
vector<int> findNextGreater(const vector<int>& nums) {
    vector<int> res(nums.size(), nums.size());
    stack<int> indices;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!indices.empty() &&
               nums[indices.top()] < nums[i]) {
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

vector<int> findPrevGreater(const vector<int>& nums) {
    vector<int> res(nums.size(), -1);
    stack<int> indices;
    for (int i = (int)nums.size() - 1; i >= 0 ; --i) {
        while (!indices.empty() &&
               nums[indices.top()] <= nums[i]) { // Note <= is to tackle the nearest because there are dublicates
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

vector<int> findNextSmaller(const vector<int>& nums) {
    vector<int> res(nums.size(), nums.size());
    stack<int> indices;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!indices.empty() &&
               nums[indices.top()] > nums[i]) {
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

vector<int> findPrevSmaller(const vector<int>& nums) {
    vector<int> res(nums.size(), -1);
    stack<int> indices;
    for (int i = (int)nums.size() - 1; i >= 0 ; --i) {
        while (!indices.empty() &&
               nums[indices.top()] >= nums[i]) { // Note <= is to tackle the nearest because there are dublicates
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

int main(int, char**) {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> ar(n, 0);
    for (int k = 1; k <= n; ++k) {
        cin >> ar[k-1];
    }
    
    vector<int> inextSmaller = findNextSmaller(ar);
    vector<int> iprevSmaller =  findPrevSmaller(ar);
    vector<int> inextGreater = findNextGreater(ar);
    vector<int> iprevGreater =  findPrevGreater(ar);

    lint res = 0;
    for (int i = 0; i < n; ++i) {
        res += ar[i] * ((inextGreater[i] - i) *1LL* (i - iprevGreater[i]) - 
            (inextSmaller[i] - i) *1LL* (i - iprevSmaller[i]));
    }
    
    cout << res << endl;
    
    return 0;
}