stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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);

}


// Faster C++ solution for the same problem (measured speedup: 5.154312830019126x):
#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);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 4.2814926376885065x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 4.24946323537427x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.044202128968603x):
#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);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 21.574316785401738x):
#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);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.038970894283561x):
#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);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.07695103838252x):
#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);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 4.281706246631177x):
#include <iostream>

#include <bits/stdc++.h>

using namespace std;

long long int a[200500]={0};

long long int l[200500]={0};

long long int r[200500]={0};

int main()

{

    register int n;

    scanf("%d",&n);

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

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

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

    {

        for(l[i]=i;l[i]>1;)

        {

            if(a[l[i]-1]>a[i])

                l[i]=l[l[i]-1];

            else

                break;

        }

    }

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

    {

        for(r[i]=i;r[i]<=n;)

        {

            if(a[r[i]+1]>a[i])

            {

                r[i]=r[r[i]+1];

            }

            else

                break;

        }

    }

    register long long int sum=0;

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

    {

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

    }

    printf("%lld",sum);

    return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 4.196301190443142x):
#pragma GCC optimize(2)

#pragma G++ optimize(2)

#include <bits/stdc++.h>

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<vector>

typedef long long ll;

const int maxn = 1e6 + 7;

const int mod = 1e9 + 7;

const int INF = 0x7fffffff;

map<ll,ll>mp;

queue<int>q1;

deque<int>q2;

stack<int>st;

ll n, m,x,y,z,h,t,temp=0,s[maxn],flag,st2[maxn],w[maxn],ans = 0, k,flag1=10,flag2=0;

ll l[maxn],r[maxn],a[maxn];

int main(){

    scanf("%lld",&n);

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

    {

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

        l[i]=0;

        r[i]=n+1;

    }

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

    {

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

            r[st.top()]=i;

            st.pop();

        }

        st.push(i);

    }

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

    {

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

            l[st.top()]=i;

            st.pop();

        }

        st.push(i);

    }

    ///for(ll i=1;i<=n;i++) cout << l[i] << " ";

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

    {

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

    }

    cout << ans;

    return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 4.2784119997464565x):
#include <iostream>

#include <cstdio>

using namespace std;



typedef long long LL;

const int N = 2e5 + 100;

struct Stack {

	int sep, idx;

};



Stack stk[N];

int n, top, a[N];

LL preSum, ans;



int main()

{

	scanf("%d", &n);

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

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

	}

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

		int x = 0;

		while ( a[ stk[ top].idx] > a[i]) {

			x += stk[top].sep;

			preSum -= (LL)stk[top].sep * a[ stk[top].idx];

			top --;

		}

		stk[ ++ top].idx = i, stk[top].sep = x + 1;

		preSum += (LL)stk[top].sep * a[ stk[top].idx];

		ans += preSum;

	}

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

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#define int long long

using namespace std;

int n,top,minn;

const int N=1000010;

int a[N],zhan[N],r[N],l[N];

long long ans;

signed main()

{

	cin>>n;

	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);

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

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

	{

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

		l[i]=zhan[top];

		zhan[++top]=i;

	}

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

	cout<<ans;

	return 0;

}

/*

8

5 4 8 1 2 6 7 3

*/

// Faster C++ solution for the same problem (measured speedup: 5.2261844967194575x):
#include <stdio.h>

#include <string.h>

#define N 200002

typedef unsigned long long LL;



int a[N], lp[N], rp[N];

LL ans;



int main()

{	

	int n, i, tp, t;

	

	scanf("%d", &n);

	for(i = 1; i <= n; i++) scanf("%d", a + i);

	a[0] = a[n + 1] = 0;

	for(lp[1] = 0, i = 2; i <= n; i++){

		tp = i - 1, t = a[i];

		while(a[tp] > t) tp = lp[tp];

		lp[i] = tp;

	}

	

	ans = (LL)a[n] * (LL)(n - lp[n]); 

	for(rp[n] = n + 1, i = n - 1; i >= 1; i--){

		tp = i + 1, t = a[i];

		while(a[tp] > t) tp = rp[tp];

		rp[i] = tp;

		ans += (LL)t * (LL)(tp - i) * (LL)(i - lp[i]);

	}

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

	

	return 0;

}