Language: C++

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

struct rmqsegtree{
  vector< pair<int, int> > t; //<data, at>
  pair<int, int> re;
  int n;
  void dflt(void){ re.first = INT_MAX; re.second = -1; return; }
  void use(void){
    int i; dflt();
    for(i = 0;;++i)if((1 << i) >= n)break;
    ++i; t.resize(1 << i); t[0].first = 1 << (i - 1); t[0].second = 1 << i;
    for(i = 1;i < t[0].second;++i)t[i] = re;
    for(i = 0;i < n;++i)t[i + t[0].first].second = i;
    return;
  }
  void build(vector<int> a){
    for(n = 1;;n <<= 1)if(n >= a.size())break;
    t.resize(n << 1); dflt();
    t[0].first = n; t[0].second = t[0].first << 1; n = a.size();
    for(int i = 1;i < t[0].second;++i)t[i] = re;
    for(int i = 0;i < n;++i){
      t[t[0].first + i].first = a[i]; t[t[0].first + i].second = i;
    }
    for(int i = t[0].first - 1;i >= 1;--i)
      t[i] = (t[i << 1] <= t[(i << 1) + 1]) ? t[i << 1] : t[(i << 1) + 1];
    return;
  }
  void update(int at, int data){
    t[t[0].first + at].first = data;
    for(int x = t[0].first + at;x > 1;){
      x >>= 1;
      if(t[x << 1].first < t[(x << 1) + 1].first)t[x] = t[x << 1];
      else t[x] = t[(x << 1) + 1];
    }
    return;
  }
  pair<int, int> query(int l, int r, int k, int kl, int kr){
    //printf("%d %d %d %d %d\n", l, r, k, kl, kr);
    if(l <= t[k].second && t[k].second < r)return t[k];
    if(k >= t.size())return re;
    if(kl >= r || kr <= l)return re;
    if(l <= kl && kr <= r)return t[k];
    pair<int, int> a = query(l, r, k << 1, kl, (kl + kr) >> 1);
    pair<int, int> b = query(l, r, k * 2 + 1, (kl + kr) >> 1, kr);
    return (a.first < b.first) ? a : b;
  }
  pair<int, int> find(int l, int r){ return query(l, r, 1, 0, t[0].first); }
  void deb(void){
    int x = 1;
    printf("t[0] = (%d, %d)\n", t[0].first, t[0].second);
    for(int i = 1;i < t[0].second;++i){
      printf("%11d", t[i].first);
      if(i == (1 << x) - 1){ puts(""); ++x; }
    }
    return;
  }
};

typedef long long ll;

vector<int> aa;
int where[200001] = {0};
int n;
rmqsegtree R;

ll solve(int mi, int l, int r){
  if(r - l == 1)return mi;
  if(r - l == 2)return aa[l] + aa[l + 1] + min(aa[l], aa[l + 1]);
  int qwe = min(where[mi] - l + 1, r - where[mi]), rty = max(where[mi] - l + 1, r - where[mi]);
  ll res = (ll)qwe * (ll)(qwe + 1);
  res += (ll)(1 + r - l - rty - 1) * (ll)(1 + r - l - rty);
  res >>= 1;
  res += (ll)qwe * (ll)(rty - qwe);
  res *= (ll)mi;
  bool isl = (where[mi] - l > 0), isr = (r - where[mi] > 1);
  if(isl)res += solve(R.find(l, where[mi]).first, l, where[mi]);
  if(isr)res += solve(R.find(where[mi] + 1, r).first, where[mi] + 1, r);
  return res;
}

signed main(void){
  scanf("%d", &n);
  aa.resize(n);
  for(int i = 0;i < n;++i){
    scanf("%d", &aa[i]);
    where[aa[i]] = i;
  }
  R.build(aa);

  printf("%lld\n", solve(1, 0, n));

  return 0;
}


Compiler output:
a.cc: In member function 'void rmqsegtree::dflt()':
a.cc:12:31: error: 'INT_MAX' was not declared in this scope
   12 |   void dflt(void){ re.first = INT_MAX; re.second = -1; return; }
      |                               ^~~~~~~
a.cc:5:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
    4 | #include<vector>
  +++ |+#include <climits>
    5 |