//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
   
//#include <x86intrin.h>
#include <bits/stdc++.h>   
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, a[N], l[N], r[N], mx[20][N], lg[N];
ll ans;
stack <int> st;

inline int get (int l, int r) {
   int len = lg[r - l + 1];
   return max (mx[len][l], mx[len][r - (1 << len) + 1]);
}

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n;
   lg[0] = -1;
   for (int i = 1; i <= n; i ++) cin >> a[i], mx[0][i] = a[i], lg[i] = lg[i / 2] + 1;   
   for (int p = 1; (1 << p) <= n; p ++)
      for (int i = 1; i + (1 << p) - 1 <= n; i ++)
         mx[p][i] = max (mx[p - 1][i], mx[p - 1][i + (1 << (p - 1))]);
   for (int i = 1; i <= n; i ++) {
      while (sz (st) && a[st.top ()] < a[i]) st.pop ();
      if (!sz (st)) l[i] = 0;
      else l[i] = st.top ();
      st.push (i);
   }
   st = stack <int> ();
   for (int i = n; i >= 1; i --) {
      while (sz (st) && a[st.top ()] < a[i]) st.pop ();
      if (!sz (st)) r[i] = n + 1;
      else r[i] = st.top ();
      st.push (i);
   }
   for (int i = 1; i <= n; i ++) {
      if (l[i] == 0 && r[i] == n + 1) continue;
      if (r[i] != n + 1) {
         int pos = n + 1;
         int L = r[i] + 1, R = n;
         while (L <= R) {
            int mid = L + R >> 1;
            if (get (r[i] + 1, mid) > a[i]) pos = mid, R = mid - 1;
            else L = mid + 1;
         }
         ans += 1ll * (i - l[i]) * (pos - r[i]) * a[i];
      }     
      if (l[i]) {
         int pos = 0;
         int L = 1, R = l[i] - 1;
         while (L <= R) {
            int mid = L + R >> 1;
            if (get (mid, l[i] - 1) > a[i]) pos = mid, L = mid + 1;
            else R = mid - 1; 
         }
         ans += 1ll * (l[i] - pos) * (r[i] - i) * a[i];
      }
   }
   cout << ans;
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
                          

Measured memory_bytes: 22272