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

#define ll long long

#define int ll

using namespace std;

ll c[55],f[250050],sz[55],fa[55];

struct node{

	ll cost,value,count;

	node(ll cost=0,ll value=0,ll count=0){this->cost=cost,this->value=value,this->count=count;}

	inline friend bool operator < (const node a,const node b){return a.cost*b.value<b.cost*a.value;}

}cs[555];

signed main(){

	ll n,x,d,ans=0;cin>>n>>x>>d;cin>>c[1];sz[1]=1;

	for(int i=2;i<=n;++i) cin>>c[i]>>fa[i],sz[i]=1;

	for(int i=n;i;--i) c[fa[i]]+=c[i],sz[fa[i]]+=sz[i];memset(f,0x3f,sizeof f);f[0]=0;

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

		int T=min(n,d);if(i==1) T=n;

		for(int bit=1;bit<=T;T-=bit,bit<<=1) for(int j=n*n*n;j>=bit*sz[i];--j) f[j]=min(f[j],f[j-bit*sz[i]]+bit*c[i]);//bit>>=1;

		for(int j=n*n*n;j>=T*sz[i];--j) f[j]=min(f[j],f[j-T*sz[i]]+T*c[i]);

		if(i==1) cs[i]=node(c[i],sz[i],1e9);

		else cs[i]=node(c[i],sz[i],max(0ll,d-n));

	}

	sort(cs+1,cs+n+1);

	for(int has=0;has<=n*n*n;++has)if(f[has]<=x){

		int las=x-f[has],res=has;

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

			int now=min(cs[i].count,las/cs[i].cost);

			res+=now*cs[i].value;las-=now*cs[i].cost;

		}

		ans=max(ans,res);

	}

	cout<<ans<<endl;

	return 0;

}

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

using namespace std;

const int N=55;

int n,x,d,fa[N],c[N*N*N];

struct node

{

	int v,id;

	long long w;

	bool operator<(const node k)const

	{

		return v*k.w>w*k.v;

	}

}a[N];

long long dp[N*N*N],ans;

int main()

{

	ios::sync_with_stdio();

	cin>>n>>x>>d;

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

	{

		cin>>a[i].w;

		if(i>1)

			cin>>fa[i];

		a[i].id=i;

		a[i].v=1;

	}

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

	{

		a[fa[i]].w+=a[i].w;

		a[fa[i]].v+=a[i].v;

	}

	sort(a+1,a+n+1);

	int m=min(n,d);

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

		dp[j]=1e18;

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

	{

		for(int j=0;j<=n*n*n;j++)

			c[j]=0;

		for(int j=0;j<=n*n*n;j++)

		{

			if(c[j]==m)

				continue;

			if(dp[j+a[i].v]>dp[j]+a[i].w)

			{

				dp[j+a[i].v]=dp[j]+a[i].w;

				c[j+a[i].v]=c[j]+1;

			}

			else if(dp[j+a[i].v]==dp[j]+a[i].w&&c[j+a[i].v]>c[j]+1)

				c[j+a[i].v]=c[j]+1;

		}

	}

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

	{

		if(dp[i]>x)

			continue;

		long long w=dp[i],v=i;

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

		{

			if(a[j].id==1)

			{

				long long zh=(x-w)/a[j].w;

				w+=zh*a[j].w,v+=zh*a[j].v;

				continue;

			}

			long long zh=min((long long)d-m,(x-w)/a[j].w);

			w+=zh*a[j].w,v+=zh*a[j].v;

		}

		ans=max(ans,v);

	}

	cout<<ans<<endl;

	return 0;

}




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

#include<cstring>

#define retrun return

#define cpnst const

int N,X,D;

typedef long long ll;

ll V[111111],W[111111],f[111111];

ll dp[133333];

cpnst int lim=131072;

void ins(ll v,ll w)

{

	register int i;

	for(i=lim;i>=w;i--)

		if(dp[i]>dp[i-w]+v)dp[i]=dp[i-w]+v;

}

struct pii

{ll v,w,s;}P[111];

bool operator<(cpnst pii x,cpnst pii y)

{return x.w*y.v>x.v*y.w;}

ll greedy(ll VAG)

{

	register int i;

	ll ret=0;

	for(i=1;i<=N;i++)

	{

		ll K=VAG/P[i].v;

		if(K>P[i].s)K=P[i].s;

		ret+=P[i].w*K,VAG-=P[i].v*K;

	}return ret;

}

void trial(ll v,ll w,int d)

{

	register int i;

	for(i=1;i<=d;d-=i,i<<=1)ins(v*i,w*i);

	if(d)ins(v*d,w*d);

}

#include<algorithm>

int main()

{

	register int i;

	scanf("%d%d%d",&N,&X,&D);

	int DL=D;

	if(N<DL)DL=N;

	scanf("%lld",V+1),W[1]=1;

	for(i=2;i<=N;i++)

		scanf("%lld%lld",V+i,f+i),W[i]=1;

	for(i=N;i>1;i--)

		V[f[i]]+=V[i],W[f[i]]+=W[i];

	for(i=1;i<=N;i++)

		P[i]=(pii){V[i],W[i],D-DL+X*(i==1)};

	std::sort(P+1,P+N+1);

	for(i=1;i<=lim;i++)dp[i]=2e9;

	for(i=1;i<=N;i++)trial(V[i],W[i],DL);

	ll ans=0;

	for(i=0;i<=lim;i++)

	{

		if(dp[i]>X)continue;

		ll T=greedy(X-dp[i])+i;

		if(T>ans)ans=T;

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

}

/*

Please don't let me down.

*/

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

using namespace std;

const int N=55;

int n,x,d,fa[N],c[N*N*N];

struct node

{

	int v,id;

	long long w;

	bool operator<(const node k)const

	{

		return v*k.w>w*k.v;

	}

}a[N];

long long dp[N*N*N],ans;

int main()

{

	ios::sync_with_stdio();

	cin>>n>>x>>d;

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

	{

		cin>>a[i].w;

		if(i>1)

			cin>>fa[i];

		a[i].id=i;

		a[i].v=1;

	}

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

	{

		a[fa[i]].w+=a[i].w;

		a[fa[i]].v+=a[i].v;

	}

	sort(a+1,a+n+1);

	int m=min(n,d);

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

		dp[j]=1e18;

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

	{

		for(int j=0;j<=n*n*n;j++)

			c[j]=0;

		for(int j=0;j<=n*n*n;j++)

		{

			if(c[j]==m)

				continue;

			if(dp[j+a[i].v]>dp[j]+a[i].w)

			{

				dp[j+a[i].v]=dp[j]+a[i].w;

				c[j+a[i].v]=c[j]+1;

			}

			else if(dp[j+a[i].v]==dp[j]+a[i].w&&c[j+a[i].v]>c[j]+1)

				c[j+a[i].v]=c[j]+1;

		}

	}

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

	{

		if(dp[i]>x)

			continue;

		long long w=dp[i],v=i;

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

		{

			if(a[j].id==1)

			{

				long long zh=(x-w)/a[j].w;

				w+=zh*a[j].w,v+=zh*a[j].v;

				continue;

			}

			long long zh=min((long long)d-m,(x-w)/a[j].w);

			w+=zh*a[j].w,v+=zh*a[j].v;

		}

		ans=max(ans,v);

	}

	cout<<ans<<endl;

	return 0;

}




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

#define maxn 55

#define LL long long

using namespace std;

int n,m,d,V,lim,ans;

LL f[maxn*maxn*maxn];

struct node{

	int v,id; LL w;

	bool operator < (const node &p)const{return v*p.w>w*p.v;}

}a[maxn];

vector<int>G[maxn];

void dfs(int u){for(int v:G[u]) dfs(v),a[u].v+=a[v].v,a[u].w+=a[v].w;}

void ins(LL v,LL w){for(int i=V;i>=v;i--) f[i]=min(f[i],f[i-v]+w);}

int main()

{

	scanf("%d%d%d%d",&n,&m,&d,&a[1].w),a[1].v=a[1].id=1;

	for(int i=2,x;i<=n;i++) scanf("%d%d",&a[i].w,&x),a[i].v=1,G[x].push_back(i);

	dfs(1);

	memset(f,0x3f,sizeof f),f[0]=0;

	V = n*n*n, lim = min(n,d);

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

		int x=lim;

		for(int j=1;j<=x;x-=j,j<<=1) ins(1ll*j*a[i].v,j*a[i].w);

		if(x) ins(1ll*x*a[i].v,x*a[i].w);

	}

	sort(a+1,a+1+n);

	while(a[n].id!=1) n--;

	for(int i=0;i<=V&&f[i]<=m;i++){

		int v=i,w=f[i];

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

			int k=min(1ll*d-lim,(m-w)/a[j].w);

			v+=k*a[j].v,w+=k*a[j].w;

		}

		int k=(m-w)/a[n].w;

		ans=max(ans,v+k*a[n].v);

	}

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

}

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

using namespace std;

const int N=55;

int n,x,d,fa[N],c[N*N*N];

struct node

{

	int v,id;

	long long w;

	bool operator<(const node k)const

	{

		return v*k.w>w*k.v;

	}

}a[N];

long long dp[N*N*N],ans;

int main()

{

	ios::sync_with_stdio();

	cin>>n>>x>>d;

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

	{

		cin>>a[i].w;

		if(i>1)

			cin>>fa[i];

		a[i].id=i;

		a[i].v=1;

	}

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

	{

		a[fa[i]].w+=a[i].w;

		a[fa[i]].v+=a[i].v;

	}

	sort(a+1,a+n+1);

	int m=min(n,d);

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

		dp[j]=1e18;

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

	{

		for(int j=0;j<=n*n*n;j++)

			c[j]=0;

		for(int j=0;j<=n*n*n;j++)

		{

			if(c[j]==m)

				continue;

			if(dp[j+a[i].v]>dp[j]+a[i].w)

			{

				dp[j+a[i].v]=dp[j]+a[i].w;

				c[j+a[i].v]=c[j]+1;

			}

			else if(dp[j+a[i].v]==dp[j]+a[i].w&&c[j+a[i].v]>c[j]+1)

				c[j+a[i].v]=c[j]+1;

		}

	}

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

	{

		if(dp[i]>x)

			continue;

		long long w=dp[i],v=i;

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

		{

			if(a[j].id==1)

			{

				long long zh=(x-w)/a[j].w;

				w+=zh*a[j].w,v+=zh*a[j].v;

				continue;

			}

			long long zh=min((long long)d-m,(x-w)/a[j].w);

			w+=zh*a[j].w,v+=zh*a[j].v;

		}

		ans=max(ans,v);

	}

	cout<<ans<<endl;

	return 0;

}




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

using namespace std;



int col[110][110];

int a[10010];



int main()

{

	ios::sync_with_stdio(false);

	int i,j,m,n,k;

	cin>>n>>m>>k;

	for(i=1;i<=k;i++)

	{

		cin>>a[i];

	}

	k=1;

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

	{

		if(i&1)

		{

			for(j=m-1;j>=0;j--)

			{

				while(a[k]==0) k++;

				col[i][j]=k;

				a[k]--;

			}

		}

		else

		{

			for(j=0;j<m;j++)

			{

				while(a[k]==0) k++;

				col[i][j]=k;

				a[k]--;

			}

		}

	}

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

	{

		for(j=0;j<m;j++)

		{

			if(j) cout<<" ";

			cout<<col[i][j]; 

		}

		cout<<"\n";

	}

	return 0;

}

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

using namespace std;

int p[10010];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int s;

    scanf("%d",&s);

    int a;

    int statu=0;

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

    {

        scanf("%d",&a);

        for(int j=0;j<a;j++,statu++)

            p[statu]=i;

    }

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

    {

        if(i%2==0)

        {

            for(int j=0;j<m-1;j++)

            printf("%d ",p[i*m+j]);

            printf("%d\n",p[(i+1)*m-1]);

        }

        else

        {

            for(int j=m-1;j>0;j--)

                printf("%d ",p[i*m+j]);

            printf("%d\n",p[i*m]);

        }

    }

    return 0;

}


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

#include <cstring>

using namespace std;



int mp[110][110];

int sa[10010];

int h, w, n;



int main() {

	while (cin >> h >> w) {

		cin >> n;

		memset(mp, 0, sizeof(mp));

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

			cin >> sa[i];

		int ii = 0, jj = 0, cc = 1;

		int cas = h * w;

		while (cas--) {

			while (sa[cc] == 0) {

				cc++;

			}

			mp[ii][jj] = cc;

			sa[cc]--;;

			if (jj % 2 == 0) {

				ii++;

				if (ii >= w) {

					ii = w - 1;

					jj++;

				}

			}else {

				ii--;

				if (ii < 0) {

					ii = 0;

					jj++;

				}

			}

		}

		for (int j = 0; j < h; j++) {

			for (int i = 0; i < w; i++) {

				if (i)

					cout << " " << mp[i][j];

				else

					cout << mp[i][j];

			}

			cout << endl;

		}

	}

	return 0;

}

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

using namespace std;

int p[10010];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int s;

    scanf("%d",&s);

    int a;

    int statu=0;

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

    {

        scanf("%d",&a);

        for(int j=0;j<a;j++,statu++)

            p[statu]=i;

    }

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

    {

        if(i%2==0)

        {

            for(int j=0;j<m-1;j++)

            printf("%d ",p[i*m+j]);

            printf("%d\n",p[(i+1)*m-1]);

        }

        else

        {

            for(int j=m-1;j>0;j--)

                printf("%d ",p[i*m+j]);

            printf("%d\n",p[i*m]);

        }

    }

    return 0;

}


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

#include <stdio.h>

using namespace std;



int main()

{

	int h, w, n, c[105][105], a[10005];

	scanf("%d%d%d", &h, &w, &n);

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

	int cur = 0;

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

	{

		if(i%2)

		{

			for(int j = w - 1; j >= 0; j--)

			{

				while(a[cur] == 0) cur++;//whileorz...

				a[cur]--;

				c[i][j] = cur + 1;

			}

		}

		else

		{

			for(int j = 0; j < w; j++)

			{

				while(a[cur] == 0) cur++;

				a[cur]--;

				c[i][j] = cur + 1;

			}

		}

	}

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

	{

		for(int j = 0; j < w; j++)

		{

			if(j)

                printf(" ");

			printf("%d", c[i][j]);

		}

		puts("");

	}

	return 0;

}


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

using namespace std;

int p[10010];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int s;

    scanf("%d",&s);

    int a;

    int statu=0;

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

    {

        scanf("%d",&a);

        for(int j=0;j<a;j++,statu++)

            p[statu]=i;

    }

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

    {

        if(i%2==0)

        {

            for(int j=0;j<m-1;j++)

            printf("%d ",p[i*m+j]);

            printf("%d\n",p[(i+1)*m-1]);

        }

        else

        {

            for(int j=m-1;j>0;j--)

                printf("%d ",p[i*m+j]);

            printf("%d\n",p[i*m]);

        }

    }

    return 0;

}


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

#include <stdio.h>

using namespace std;



int main()

{

	int h, w, n, c[105][105], a[10005];

	scanf("%d%d%d", &h, &w, &n);

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

	int cur = 0;

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

	{

		if(i%2)

		{

			for(int j = w - 1; j >= 0; j--)

			{

				if(a[cur] == 0) cur++;

				a[cur]--;

				c[i][j] = cur + 1;

			}

		}

		else

		{

			for(int j = 0; j < w; j++)

			{

				if(a[cur] == 0) cur++;

				a[cur]--;

				c[i][j] = cur + 1;

			}

		}

	}

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

	{

		for(int j = 0; j < w; j++)

		{

			if(j)

                printf(" ");

			printf("%d", c[i][j]);

		}

		puts("");

	}

	return 0;

}


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

using namespace std;

int p[10010];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int s;

    scanf("%d",&s);

    int a;

    int statu=0;

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

    {

        scanf("%d",&a);

        for(int j=0;j<a;j++,statu++)

            p[statu]=i;

    }

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

    {

        if(i%2==0)

        {

            for(int j=0;j<m-1;j++)

            printf("%d ",p[i*m+j]);

            printf("%d\n",p[(i+1)*m-1]);

        }

        else

        {

            for(int j=m-1;j>0;j--)

                printf("%d ",p[i*m+j]);

            printf("%d\n",p[i*m]);

        }

    }

    return 0;

}


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



using namespace std;



typedef long long int ll;

typedef string str;

typedef pair<ll,ll> pll;

typedef vector<ll> vll;



#define X first

#define Y second

#define PB push_back

#define For(i,a,b) for (int i=a;i<b;i++)

#define Ford(i,a,b) for (int i=a;i>=b;i--)

#define smax(a,b) a=max(a,b)

#define smin(a,b) a=min(a,b)

#define SZ(a) ((ll)a.size())

#define E(a) cout << #a << ' ' << a << '\n'





const ll M=5e5+5,LG=17,inf=1e18;



int n,m;



pll seg[M];



pll get(ll l,ll r)

{

	pll res={inf,0};

	for (;l<r;l/=2,r/=2)

	{

		if (l&1) smin(res,seg[l++]);

		if (r&1) smin(res,seg[--r]);

	}

	return res;

}



ll calc(ll l,ll r)

{

	if (l==r)

		return 0;

	pll x=get(l,r);

	return calc(l,x.Y)+calc(x.Y+1,r)+x.X*(x.Y-l+1)*(r-x.Y);

}



int main()

{

	cin >> n;

	ll s=0;

	For(i,0,n)

	{

		cin >> seg[i+n].X;

		seg[i+n].Y=i+n;

	}

	Ford(i,n-1,0)

	{

		seg[i]=min(seg[2*i],seg[2*i+1]);

	}

	cout << calc(n,2*n);

}


// 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<bits/stdc++.h>

#define endl '\n'

#define N 200005

using namespace std;



struct kieu{long gt,vt;};

kieu st[N];

long  a[N], n,so,kq;



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

	cin>>n;

	st[0]={0,0}; so=0;

	for(long i=1;i<=n;++i) cin>>a[i];

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

		while(a[i]<st[so].gt){

			kq+=st[so].gt*(i-st[so].vt)*(st[so].vt-st[so-1].vt);

			--so;

		}

		st[++so]={a[i],i};

	}

	cout<<kq;

}

// 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 <bits/stdc++.h>

using namespace std;

typedef long long int ll;

typedef pair<int,int> pii;

typedef pair<ll,ll>pll;

const int INF = 1e9;

const ll LINF = 1e18;



int main()

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N;

    cin >> N;

    vector<ll> b(N+1,0);

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

    {

        ll a;

        cin >> a;

        b[a] = i;

    }

    set<ll> s;

    s.insert(0);

    s.insert(N+1);

    ll ans=0;

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

    {

        auto it = s.lower_bound(b[i]);

        ans += i*(*it-b[i]) * (b[i] - *(--it));

        s.insert(b[i]);

    }

    cout << ans << endl;

    return 0;

}

// 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):
//In the name of God

#include<bits/stdc++.h>



using namespace std;



const int N = 2e5 + 10;

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

stack<int> st1, st2;

long long res;



int main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	cin >> n;

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

		cin >> a[i];

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

		l[i] = -1;

		while(st1.size() && a[st1.top()] > a[i])

			st1.pop();

		if(st1.size())

			l[i] = st1.top();

		st1.push(i);

	}

	for(int i=n-1; ~i; --i){

		r[i] = n;

		while(st2.size() && a[st2.top()] > a[i])

			st2.pop();

		if(st2.size())

			r[i] = st2.top();

		st2.push(i);

	}

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

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

	cout << res;

	return 0;

}

// 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<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200000

#define LL long long

int stk[MAXN+5];

int n,top;

LL a[MAXN+5],d[MAXN+5],ans;

int main()

{

	scanf("%d",&n);

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

	{

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

		while(a[stk[top]]>=a[i])top--;

		d[i]=stk[top];stk[++top]=i;

	}

	top=0,stk[0]=n+1;

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

	{

		while(a[stk[top]]>=a[i])top--;

		ans+=a[i]*(i-d[i])*(stk[top]-i);stk[++top]=i;

	}

	printf("%lld",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 <bits/stdc++.h>



using namespace std;



#define ll64 long long



int main()

{

    set<int> S;

    map<int, int> IDX;

    int N;

    scanf("%d", &N);

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

        int x;

        scanf("%d", &x);

        IDX[x] = i;

    }

    S.insert(0);

    S.insert(N + 1);

    ll64 ans = 0;

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

        int m = IDX[i];

        auto it = S.upper_bound(m);

        ll64 y = *it;

        it--;

        ll64 x = *it;

        ans += (m - x) * (y - m) * i;

        S.insert(m);

        //printf("%d %d %d\n", x, m, y);

    }

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

}


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

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXN 200002

int n,a[MAXN],pos[MAXN],pre[MAXN],nex[MAXN];

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++)

		pre[i]=i-1,nex[i]=i+1;

	long long ans=0;

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

	{

		int j=pos[i];

		ans+=i*1LL*(j-pre[j])*(nex[j]-j);

		pre[nex[j]]=pre[j];

		nex[pre[j]]=nex[j];

	}

	printf("%lld",ans);

}

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

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int MAXN=1234567;

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

int main() {

  int n;

  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;

    }

    long long ans=0;

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

	{

		int j=pos[i];

		ans+=i*1LL*(j-pr[j])*(ne[j]-j);

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

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

    }

  cout<<ans<<endl;

  return 0;

}


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

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXN 200002

int n,a[MAXN],pos[MAXN],pre[MAXN],nex[MAXN];

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++)

		pre[i]=i-1,nex[i]=i+1;

	long long ans=0;

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

	{

		int j=pos[i];

		ans+=i*1LL*(j-pre[j])*(nex[j]-j);

		pre[nex[j]]=pre[j];

		nex[pre[j]]=nex[j];

	}

	printf("%lld",ans);

}

// Fastest known solution for this problem: