Min Subarray

#include <bits/stdc++.h>
#define f(i,a,b) for(int i = (a); i <= (b); i++)

typedef long long ll;
using namespace std;

int N, Par[200005], L[200005], R[200005], In[200005];
pair<int,int> A[200005];

int find(int n)
{
    if(Par[n] == n) return n;
    else return Par[n] = find(Par[n]);
}

void join(int a, int b)
{
    int ca = find(a), cb = find(b);
    L[ca] = min(L[ca],L[cb]);
    R[ca] = max(R[ca],R[cb]);
    Par[cb] = ca;
}

int main()
{
    cin >> N;
    f(i,1,N) scanf("%d", &A[i].first);
    f(i,1,N) A[i].second = i;
    sort(A+1,A+N+1,greater<pair<int,int>>());

    f(i,1,N) L[i] = R[i] = i, Par[i] = i;
    ll ans = 0;

    f(p,1,N)
    {
        int x = A[p].first, i = A[p].second;
        if(In[i-1] && find(i-1) != find(i)) join(i-1,i);
        if(In[i+1] && find(i+1 != find(i))) join(i+1,i);

        int c = find(i);
        ll left = i - L[c] + 1;
        ll right = R[c] - i + 1;
        ans += left*right*x;

        In[i] = 1;
    }

    cout << ans;
}