/********************************************************************* 程序名: 版权: Joecai 作者: Joecai 日期: 2022-04-30 00:10 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 5e5 + 10, INF = 0x3f3f3f3f; int n; int a[N]; stack<int>s; int l1[N];//左边区间的最大值 int l2[N]; int r1[N];//右边区间的最小值 int r2[N]; void solve() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) //单调递减的栈 左闭右开防止被选两次 { while (s.size() && a[s.top()] <= a[i]) s.pop(); if (s.size() == 0) { l1[i] = i; } else { l1[i] = i - s.top(); } s.push(i); } while (s.size()) s.pop(); for (int i = n; i >= 1; i--) { while (s.size() && a[s.top()] < a[i]) s.pop(); if (s.size() == 0) { r1[i] = n - i + 1; } else { r1[i] = s.top() - i; } s.push(i); } while (s.size()) s.pop(); for (int i = 1; i <= n; i++) { while (s.size() && a[s.top()] >= a[i]) s.pop(); if (s.size()) { l2[i] = i - s.top(); } else { l2[i] = i; } s.push(i); } while (s.size()) s.pop(); for (int i = n; i >= 1; i--) { while (s.size() && a[s.top()] > a[i]) s.pop(); if (s.size()) { r2[i] = s.top() - i; } else { r2[i] = n - i + 1; } s.push(i); } int ans = 0; for (int i = 1; i <= n; i++) { ans += a[i] * ((l1[i]) * (r1[i]) - (l2[i]) * (r2[i])); } cout << ans << endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }