daimayuan#436. 子串的最大差（单调栈）

/*********************************************************************
    程序名:
    版权: 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;
}