stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#include<cstdio>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();

	int A[200001];

	rep1(i, N) A[getint()] = i;



	int dai[200002], shou[200002];

	rep1(i, N) {

		dai[i + 1] = i;

		shou[i - 1] = i;

	}



	ll kotae = 0;

	for (int i = N; i > 0; i--) {

		int a = A[i];

		int l = shou[a - 1];

		int r = dai[a + 1];

		kotae += (ll)(a - l + 1) * (r - a + 1) * i;

		dai[l] = r;

		shou[r] = l; cesp(l); cesp(r); ce(kotae);

	}



	printf("%lld", kotae);



	Would you please return 0;

}

// Optimized solution to the same problem (faster):
//#include<bits/stdc++.h>

#include<cstdio>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();

	int A[200001];

	rep1(i, N) A[getint()] = i;



	int dai[200002], shou[200002];

	rep1(i, N) {

		dai[i + 1] = i;

		shou[i - 1] = i;

	}



	ll kotae = 0;

	for (int i = N; i > 0; i--) {

		int a = A[i];

		int l = shou[a - 1];

		int r = dai[a + 1];

		kotae += (ll)(a - l + 1) * (r - a + 1) * i;

		dai[l] = r;

		shou[r] = l;

	}



	printf("%lld", kotae);



	Would you please return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



const int maxn = 2e6+10;

int n;

ll a[maxn];

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1



ll minv[maxn<<2];

void build(int l,int r,int rt){

    if(l==r){

        scanf("%lld",a+l);

        minv[rt]=a[l];return;

    }

    int mid=l+r>>1;

    build(lson);build(rson);

    minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r)return minv[rt];

    int mid=l+r>>1,ret=0x3f3f3f3f;

    if(L<=mid)ret=min(ret,query(L,R,lson));

    if(R>mid)ret=min(ret,query(L,R,rson));

    return ret;

}



int main(){

    int t=1;//cin>>t;

    while(t--){

        scanf("%d",&n);

        build(1,n,1);

        ll ans=0;

        int l,r,mid;

        ll len1,len2;

        for(int i=1;i<=n;i++){

            l=0,r=i+1;

            while(r-l>1){

                mid=l+r>>1;

                if(query(mid,i,1,n,1)==a[i])r=mid;

                else l=mid;

            }

            len1=i-r+1;

            l=i-1,r=n+1;

            while(r-l>1){

                mid=l+r>>1;

                if(query(i,mid,1,n,1)==a[i])l=mid;

                else r=mid;

            }

            len2=l-i+1;

            ans+=1ll*a[i]*len1*len2;

        }

        cout<<ans<<endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cctype>

using namespace std;

typedef long long int64;

inline int read(int f = 1, int x = 0, char ch = ' ')

{

    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;

    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();

    return f*x;

}

const int N = 2e5+5;

int n, p[N], s[N], top, f[N], g[N];

int64 ans;

int main()

{

    n = read(); 

    for(int i = 1; i <= n; ++i) p[i] = read();

    top = 0;

    for(int i = 1; i <= n; ++i) 

    {

        while(top&&p[s[top]] > p[i]) --top;

        f[i] = i-s[top], s[++top] = i;

    }

    top = 0; s[0] = n+1;

    for(int i = n; i; --i)

    {

        while(top&&p[s[top]] > p[i]) --top;

        g[i] = s[top]-i, s[++top] = i;

    }

    for(int i = 1; i <= n; ++i) ans += 1ll*f[i]*g[i]*p[i];

    printf("%lld\n", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// be name khoda

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define pb push

const ll maxn=3*1e5+5;

stack <ll> s,s1;

ll a[maxn],stt[maxn],ttt[maxn];

int main()

{

        ios::sync_with_stdio(false);ll n;cin >> n;for(ll i=1; i<=n; i++){cin >> a[i];if(!s.empty()){ll k=0;while(!s.empty() && s.top()>a[i]){ll XD;XD=s1.top();ttt[XD]=k+1;k+=stt[XD];s.pop();s1.pop();}stt[i]=k+1;s.push(a[i]);s1.push(i);}else{stt[i]=1;s.push(a[i]);s1.push(i);}}ll k=0;while(!s.empty()){ll XD;XD=s1.top();ttt[XD]=k+1;k+=stt[XD];s.pop();s1.pop();}ll ans=0;for(ll i=1; i<=n; i++){ans+=stt[i]*ttt[i]*a[i];}cout << ans;

}

// bikari


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

#define LL long long

LL ans;

int a[MAXN],b[MAXN],n,fa[MAXN],siz[MAXN];

int Find(int x)

{

	return fa[x]==x?x:fa[x]=Find(fa[x]);

}

void Union(int u,int v)

{

	u=Find(u),v=Find(v);

	if(u==v) return;

	fa[u]=v;

	siz[v]+=siz[u];

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		fa[i]=i,siz[i]=1;

		scanf("%d",&a[i]);

		b[a[i]]=i;

	}

	for(int i=n;i>=1;i--)

	{

		int p=b[i],sl=1,sr=1;

		if(a[p-1]>a[p])

		{

			sl+=siz[Find(a[p-1])];

			Union(a[p],a[p-1]);

		}

		if(a[p+1]>a[p])

		{

			sr+=siz[Find(a[p+1])];

			Union(a[p],a[p+1]);

		}

		ans+=1LL*i*sl*sr;

	}

	printf("%lld\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// Example program

#include <bits/stdc++.h>



using namespace std;



const int MAXN = 2e5 + 1;



typedef long long int ll;



ll dp[MAXN];

ll a[MAXN];

ll b[MAXN];

ll c[MAXN];





int main()

{

    ll n;

    cin >> n;

    for (ll i = 0 ; i < n; i++)

    {

        cin >> a[i];

        c[a[i]] = i;

    }

    ll cnt = 0;

    b[cnt] = a[0];

    cnt++;

    ll m = a[0];

    dp[a[0]] = a[0];

    for (int i = 1; i < n; i++)

    {

        ll x = c[a[i]] - c[b[cnt - 1]];

        while (cnt > 0)

        {

            if (b[cnt - 1] < a[i])

            {

                dp[a[i]] = (x * a[i]) + dp[b[cnt - 1]];

                break;

            }

            else

            {

                if (cnt > 1)

                {

                    x += c[b[cnt - 1]] - c[b[cnt - 2]];

                }

                else

                    x += c[b[cnt - 1]] + 1;

                cnt--;

            }

        }

        if (cnt == 0)

        {

            dp[a[i]] = (x * a[i]);

        }

        m += dp[a[i]];

        b[cnt] = a[i];

        cnt++;

    }

    cout << m;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

#define LL long long

LL ans;

int a[MAXN],b[MAXN],n,fa[MAXN],siz[MAXN];

int Find(int x)

{

	return fa[x]==x?x:fa[x]=Find(fa[x]);

}

void Union(int u,int v)

{

	u=Find(u),v=Find(v);

	if(u==v) return;

	fa[u]=v;

	siz[v]+=siz[u];

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		fa[i]=i,siz[i]=1;

		scanf("%d",&a[i]);

		b[a[i]]=i;

	}

	for(int i=n;i>=1;i--)

	{

		int p=b[i],sl=1,sr=1;

		if(a[p-1]>a[p])

		{

			sl+=siz[Find(a[p-1])];

			Union(a[p],a[p-1]);

		}

		if(a[p+1]>a[p])

		{

			sr+=siz[Find(a[p+1])];

			Union(a[p],a[p+1]);

		}

		ans+=1LL*i*sl*sr;

	}

	printf("%lld\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



#define ll long long

#define pb push_back



using namespace std;



const ll N = 1e6 + 20;

ll l[N],r[N],a[N],res,x[N];

vector<ll> st;



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin>>n;

    for(int i=0;i<n;i++)

        cin>>a[i];

    for(int i=0;i<n;i++)

    {

        while(!st.empty() && a[st.back()] >= a[i])

            st.pop_back();

        if(!st.empty())

            l[i]=st.back();

        else

            l[i] = -1;

        st.pb(i);

    }

    st.clear();

    for(int i=n-1;i>-1;i--)

    {

        while(!st.empty() && a[st.back()] > a[i])

            st.pop_back();

        if(!st.empty())

            r[i]=st.back();

        else

            r[i]=n;

        st.pb(i);

    }

    for(int i=0;i<n;i++)

    {

        r[i]--;

        l[i]++;

        res+=(r[i]-i+1)*(i-l[i]+1)*a[i];

    }

    cout<<res<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200010

#define LL long long

LL ans;

int a[MAXN],b[MAXN],n,fa[MAXN],siz[MAXN];

int Find(int x)

{

	return fa[x]==x?x:fa[x]=Find(fa[x]);

}

void Union(int u,int v)

{

	u=Find(u),v=Find(v);

	if(u==v) return;

	fa[u]=v;

	siz[v]+=siz[u];

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		fa[i]=i,siz[i]=1;

		scanf("%d",&a[i]);

		b[a[i]]=i;

	}

	for(int i=n;i>=1;i--)

	{

		int p=b[i],sl=1,sr=1;

		if(a[p-1]>a[p])

		{

			sl+=siz[Find(a[p-1])];

			Union(a[p],a[p-1]);

		}

		if(a[p+1]>a[p])

		{

			sr+=siz[Find(a[p+1])];

			Union(a[p],a[p+1]);

		}

		ans+=1LL*i*sl*sr;

	}

	printf("%lld\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<climits>

#define int long long

using namespace std;

inline int read(){

	int f=1,ans=0;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}

	return f*ans;

}

const int MAXN=200001;

int st[MAXN][21],n,a[MAXN];

int Query(int l,int r){

	int k=log2(r-l+1);

	return min(st[l][k],st[r-(1<<k)+1][k]);

}

int Ql(int x){

	int l=1,r=x-1,minn=INT_MAX;

	while(l<=r){

		int mid=l+r>>1;

		if(Query(mid,x-1)>a[x]) r=mid-1,minn=min(minn,mid);

		else l=mid+1;

	}return minn;

}

int Qr(int x){

	int l=x+1,r=n,maxn=	INT_MIN;

	while(l<=r){

		int mid=l+r>>1;

		if(Query(x+1,mid)>=a[x]) l=mid+1,maxn=max(maxn,mid);

		else r=mid-1; 

	}return maxn;

}int ans;

signed main(){

//	freopen("6.in","r",stdin);

	n=read();

	for(int i=1;i<=n;i++) a[i]=st[i][0]=read();

	for(int j=1;j<=log2(n);j++)

		for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

	for(int i=1;i<=n;i++){

		int l=Ql(i),r=Qr(i);

		if(l==INT_MAX) l=i;

		if(r==INT_MIN) r=i;

		int lena=i-l,lenb=r-i;

		ans+=(lena+lenb+1+lena*lenb)*a[i];

	}printf("%lld\n",ans);

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#define MAXN 200005

#define LL long long

int n,a[MAXN],pos[MAXN],pr[MAXN],ne[MAXN];

LL ans;

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

        pos[a[i]]=i;

    }

    for(int i=0;i<=n+1;i++)

        pr[i]=i-1,ne[i]=i+1;//pr是i的影响区间的左端点(不含) ne是右端点(不含) 注意是不含！！！

    for(int i=n;i>=1;i--)//n的排列 倒着来

    {

        int j=pos[i];

        ans+=1LL*i*(j-pr[j])*(ne[j]-j);//统计区间个数时要注意端点时不含的

        pr[ne[j]]=pr[j];

        ne[pr[j]]=ne[j];

        //核心 用当前这个值依次更新其它数的影响区间 很巧妙

        //由于是倒着来的，那么如果被更新的值要大于当前数，则没有影响，因为被更新的贡献已经算完了

        //所以就假设这些数都小于当前数 而当前数的影响区间内的所有数都要大于它自己，也大于被更新数，所以可以更新区间

    }

    printf("%lld\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstring>

using namespace std;

long long a[401000],stack[401000],l[401000],r[401000],s[401000];

int main()

{

	long long n;

	cin>>n;

	for(long long i=1; i<=n; i++)

	{

		cin>>a[i];

		s[i]=s[i-1]+a[i];

	}

	

	long long top=0;

	for(long long i=1; i<=n; i++)

	{

		while(top&&a[i]<=a[stack[top]])

		{

			top--;

		}

		l[i]=stack[top]+1;

		top++;

		stack[top]=i;

	}

	memset(stack,0,sizeof(stack));

	top=0;

	for(long long i=n; i>=1; i--)

	{

		while(top&&a[i]<=a[stack[top]])

		{

			top--;

		}

		r[i]=stack[top]-1;

		top++;

		stack[top]=i;

	}

	long long ans=0;

	for(long long i=1; i<=n; i++)

	{

		long long left=l[i],right=r[i];

		if(right==-1) right=n;

		ans+=(i-left+1)*a[i]*(right-i+1);

	}

	cout<<ans;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

const int maxn=2e5+6;

#define read(a) scanf("%I64d",&a)

#define rep(a,b,c) for(int a=b;a<=c;a++)

#define per(a,b,c) for(int a=b;a>=c;a--)

#define ls rt<<1

#define rs rt<<1|1

#define mid ((l+r)>>1)

#define int long long

template<class T>inline T max(T a,T b) { return a>b?a:b; }

template<class T>inline T min(T a,T b) { return a<b?a:b; }

int n,a[maxn],lans[maxn],rans[maxn];

struct Segment_Tree {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=max(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=0;

		if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=max(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=0; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}t;

struct Segment_Tree_ {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=min(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=maxn;

		if(L<=mid) ans=min(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=min(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=n+1; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}T;

int ans;

signed main() {

	read(n);

	rep(i,1,n) read(a[i]);

	rep(i,1,n) {

		t.insert(1,1,n,a[i],i);

		if(a[i]!=1) lans[i]=t.query(1,1,n,1,a[i]-1);

		else lans[i]=0;

	}

	T.build(1,1,n);

	per(i,n,1) {

		T.insert(1,1,n,a[i],i);

		if(a[i]!=1) rans[i]=T.query(1,1,n,1,a[i]-1);

		else rans[i]=n+1;

	}

	rep(i,1,n) ans+=(i-lans[i])*(rans[i]-i)*a[i];

	printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

#define MAX 200200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,a[MAX],Q[MAX],top;

int l[MAX],r[MAX];

ll ans;

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read(),l[i]=1,r[i]=n;

	top=0;

	for(int i=1;i<=n;++i)

	{

		while(top&&a[Q[top]]>a[i])--top;

		if(top)l[i]=Q[top]+1;

		Q[++top]=i;

	}

	top=0;

	for(int i=n;i>=1;--i)

	{

		while(top&&a[Q[top]]>a[i])--top;

		if(top)r[i]=Q[top]-1;

		Q[++top]=i;

	}

	for(int i=1;i<=n;++i)ans+=1ll*(i-l[i]+1)*(r[i]-i+1)*a[i];

	cout<<ans<<endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

const int maxn=2e5+6;

#define read(a) scanf("%I64d",&a)

#define rep(a,b,c) for(int a=b;a<=c;a++)

#define per(a,b,c) for(int a=b;a>=c;a--)

#define ls rt<<1

#define rs rt<<1|1

#define mid ((l+r)>>1)

#define int long long

template<class T>inline T max(T a,T b) { return a>b?a:b; }

template<class T>inline T min(T a,T b) { return a<b?a:b; }

int n,a[maxn],lans[maxn],rans[maxn];

struct Segment_Tree {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=max(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=0;

		if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=max(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=0; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}t;

struct Segment_Tree_ {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=min(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=maxn;

		if(L<=mid) ans=min(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=min(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=n+1; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}T;

int ans;

signed main() {

	read(n);

	rep(i,1,n) read(a[i]);

	rep(i,1,n) {

		t.insert(1,1,n,a[i],i);

		if(a[i]!=1) lans[i]=t.query(1,1,n,1,a[i]-1);

		else lans[i]=0;

	}

	T.build(1,1,n);

	per(i,n,1) {

		T.insert(1,1,n,a[i],i);

		if(a[i]!=1) rans[i]=T.query(1,1,n,1,a[i]-1);

		else rans[i]=n+1;

	}

	rep(i,1,n) ans+=(i-lans[i])*(rans[i]-i)*a[i];

	printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int g=200005;

int n,a[g],b[g],m;

long long s;



int main()

{

	//freopen("in","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		for(;a[i]<a[b[m]];m--)

			s+=(long long)a[b[m]]*(b[m]-b[m-1])*(i-b[m]);

		b[++m]=i;

	}

	for(;m;m--)

		s+=(long long)a[b[m]]*(b[m]-b[m-1])*(n-b[m]+1);

	printf("%lld",s);

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

const int maxn=2e5+6;

#define read(a) scanf("%I64d",&a)

#define rep(a,b,c) for(int a=b;a<=c;a++)

#define per(a,b,c) for(int a=b;a>=c;a--)

#define ls rt<<1

#define rs rt<<1|1

#define mid ((l+r)>>1)

#define int long long

template<class T>inline T max(T a,T b) { return a>b?a:b; }

template<class T>inline T min(T a,T b) { return a<b?a:b; }

int n,a[maxn],lans[maxn],rans[maxn];

struct Segment_Tree {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=max(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=0;

		if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=max(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=0; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}t;

struct Segment_Tree_ {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=min(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=maxn;

		if(L<=mid) ans=min(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=min(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=n+1; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}T;

int ans;

signed main() {

	read(n);

	rep(i,1,n) read(a[i]);

	rep(i,1,n) {

		t.insert(1,1,n,a[i],i);

		if(a[i]!=1) lans[i]=t.query(1,1,n,1,a[i]-1);

		else lans[i]=0;

	}

	T.build(1,1,n);

	per(i,n,1) {

		T.insert(1,1,n,a[i],i);

		if(a[i]!=1) rans[i]=T.query(1,1,n,1,a[i]-1);

		else rans[i]=n+1;

	}

	rep(i,1,n) ans+=(i-lans[i])*(rans[i]-i)*a[i];

	printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n;

long long read(){

    long long x=0,y=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(ch=='-')y=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*y;

}

long long a[2000010];

long long st[2000010];

long long l[2000010],r[2000010];

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	    a[i]=read();

	int top=0;

	for(int i=1;i<=n;i++) l[i]=0,r[i]=n+1;

	for(int i=1;i<=n;i++){

		while(top&&a[st[top]]>=a[i]) r[st[top--]]=i;

		l[i]=st[top];

		st[++top]=i;

	}

	long long ans=0;

	for(int i=1;i<=n;i++)

	    ans+=(long long)((r[i]-i)*(i-l[i])*a[i]);

	printf("%lld",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

const int maxn=2e5+6;

#define read(a) scanf("%I64d",&a)

#define rep(a,b,c) for(int a=b;a<=c;a++)

#define per(a,b,c) for(int a=b;a>=c;a--)

#define ls rt<<1

#define rs rt<<1|1

#define mid ((l+r)>>1)

#define int long long

template<class T>inline T max(T a,T b) { return a>b?a:b; }

template<class T>inline T min(T a,T b) { return a<b?a:b; }

int n,a[maxn],lans[maxn],rans[maxn];

struct Segment_Tree {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=max(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=0;

		if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=max(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=0; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}t;

struct Segment_Tree_ {

	int val[maxn<<2];

	inline void pushup(int rt) { val[rt]=min(val[ls],val[rs]); }

	inline void insert(int rt,int l,int r,int k,int ch) {

		if(l==r) return(void)(val[rt]=ch);

		if(k<=mid) insert(ls,l,mid,k,ch);

		else insert(rs,mid+1,r,k,ch);

		pushup(rt);

	}

	inline int query(int rt,int l,int r,int L,int R) {

		if(L<=l&&r<=R) return val[rt];

		int ans=maxn;

		if(L<=mid) ans=min(ans,query(ls,l,mid,L,R));

		if(R>mid) ans=min(ans,query(rs,mid+1,r,L,R));

		return ans;

	}

	inline void build(int rt,int l,int r) {

		val[rt]=n+1; if(l==r) return;

		build(ls,l,mid); build(rs,mid+1,r);

	}

}T;

int ans;

signed main() {

	read(n);

	rep(i,1,n) read(a[i]);

	rep(i,1,n) {

		t.insert(1,1,n,a[i],i);

		if(a[i]!=1) lans[i]=t.query(1,1,n,1,a[i]-1);

		else lans[i]=0;

	}

	T.build(1,1,n);

	per(i,n,1) {

		T.insert(1,1,n,a[i],i);

		if(a[i]!=1) rans[i]=T.query(1,1,n,1,a[i]-1);

		else rans[i]=n+1;

	}

	rep(i,1,n) ans+=(i-lans[i])*(rans[i]-i)*a[i];

	printf("%lld",ans);

}

// Fastest known solution for this problem: