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

}


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

}

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

}

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

}

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

}

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

}


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

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

}


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

}
// Slower C++ solution:
//#include<bits/stdc++.h>

#include<cstdio>

#include<algorithm>

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;

}



const int K = 19;

const int KM = 1 << (K - 1);

pair<int, int> dat[1 << K];



pair<int, int> check(int L, int R, int A, int l, int r) {

	if (L <= l && r <= R) return dat[A];

	if (r <= L || R <= l) return mp(1e9, 1e9);

	return min(check(L, R, A * 2, l, (l + r) / 2), check(L, R, A * 2 + 1, (l + r) / 2, r));

}



pair<int, int> query(int L, int R) {

	return check(L, R, 1, 0, KM);

}



ll kotae;

void keisan(int L, int R) {

	auto p = query(L, R);

	ll k2 = (ll)(R - L + 1) * (R - L) - (ll)(R - p.second - 1) * (R - p.second) - (ll)(p.second - L + 1) * (p.second - L);

	kotae += p.first * k2 / 2;

	if (L < p.second) keisan(L, p.second);

	if (R > p.second + 1) keisan(p.second + 1, R);

}



int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();

	rep(i, N) {

		int a = getint();

		dat[i + KM] = mp(a, i);

	}



	for (int i = KM - 1; i >= 1; i--) {

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

	}



	keisan(0, N);



	printf("%lld", kotae);



	Would you please return 0;

}

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

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

}

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

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

}

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

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


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

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

}


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

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

}


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

}