#include <iostream>
                                #include <iomanip>
                                #include <sstream>
                                #include <cstring>
                                #include <vector>
                                #include <deque>
                                #include <queue>
                                #include <set>
                                #include <map>
                                #include <valarray>
                                #include <iterator>
                                #include <functional>
                                #include <limits>
                                #include <algorithm>
                                #include <numeric>
                                #include <cmath>
                                #include <cassert>
                                #include <unordered_map>
                                #include <unordered_set>
                                #include <stack>
                                using namespace std;
                                #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
                                 #define trace(x) cerr << #x << ": " << x << " " << endl;
                             
                                typedef int64_t ll;
                             
                                #define endl '\n'
                                #define int ll
                                ll mod=1e9+7;
                                ll mod1=1e9+5;
                                
                                ll power(ll a,ll b)
                                {
                                    if(b==0) return 1;
                                    else if(b%2==0)
                                        return power((((a%mod)*(a%mod))%mod),b/2)%mod;
                                    else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
                                }
                            
                             
                                int brute(int n,int a[])
                                {
                                    int ans=0;
                                    for(int i=1;i<=n;++i)
                                    {
                                        vector<int> v;
                                        v.push_back(a[i]);
                                        for(int j=i+1;j<=n;++j)
                                        {
                                            v.push_back(a[j]);
                                            sort(v.begin(),v.end(),greater<int>());
                                            ans+=v[1];
                                        }
                                    }
                                    return ans;
                                }
                                int tree[500001];
                                int tree1[500001];
                                void update(int node, int start, int end, int idx, int val)
                                {
                                    if(start == end)
                                    {
                                        tree[node] = val;
                                    }
                                    else
                                    {
                                        int mid = (start + end) / 2;
                                        if(start <= idx and idx <= mid)
                                        {
                                           
                                            update(2*node, start, mid, idx, val);
                                        }
                                        else
                                        {
                                           
                                            update(2*node+1, mid+1, end, idx, val);
                                        }
                                        
                                        tree[node] = min(tree[2*node] , tree[2*node+1]);
                                    }
                                }
                                void update1(int node, int start, int end, int idx, int val)
                                {
                                    if(start == end)
                                    {
                                        tree1[node] = val;
                                    }
                                    else
                                    {
                                        int mid = (start + end) / 2;
                                        if(start <= idx and idx <= mid)
                                        {
                                           
                                            update1(2*node, start, mid, idx, val);
                                        }
                                        else
                                        {
                                           
                                            update1(2*node+1, mid+1, end, idx, val);
                                        }
                                        
                                        tree1[node] = max(tree1[2*node] , tree1[2*node+1]);
                                    }
                                }
                                int query(int node, int start, int end, int l, int r)
                                {
                                    if(r < start or end < l)
                                    {
                                      
                                        return 1e15;
                                    }
                                    if(l <= start and end <= r)
                                    {
                                        
                                        return tree[node];
                                    }
                                   
                                    int mid = (start + end) / 2;
                                    int p1 = query(2*node, start, mid, l, r);
                                    int p2 = query(2*node+1, mid+1, end, l, r);
                                    return min(p1 , p2);
                                }

                                int query1(int node, int start, int end, int l, int r)
                                {
                                    if(r < start or end < l)
                                    {
                                      
                                        return 0;
                                    }
                                    if(l <= start and end <= r)
                                    {
                                        
                                        return tree1[node];
                                    }
                                   
                                    int mid = (start + end) / 2;
                                    int p1 = query1(2*node, start, mid, l, r);
                                    int p2 = query1(2*node+1, mid+1, end, l, r);
                                    return max(p1 , p2);
                                }
                                

                            int32_t main()
                            {
                                IOS
                               
                                int n;
                                cin>>n;
                                vector<pair<int,int>> v[n+10];
                                int a[n+10];
                                
                                for(int i=1;i<=n;++i)
                                    {
                                        cin>>a[i];
                                        update(1,1,n,a[i],i);
                                        update1(1,1,n,i,0);
                                    }
                                    
                                    
                                   
                                    int ans=0;
                                    
                                    for(int i=1;i<=n;++i)
                                    {                    
                                        update(1,1,n,a[i],1e15);                    
                                        for(int j=0;j<v[i].size();++j)
                                        {
                                            int num=v[i][j].first;
                                            int pos=v[i][j].second;
                                            if(query(1,1,n,num+1,n)==1e15)
                                            {
                                               
                                                ans+=(n-i+1)*num*pos;
                                            }
                                            else
                                            {
                                                int x=query(1,1,n,num+1,n);
                                               
                                                
                                                ans+=(x-i)*num*pos;
                                            }
                                        }
                                        update1(1,1,n,a[i],i);
                                        
                                        if(query(1,1,n,a[i]+1,n)==1e15)
                                            continue;
                                        else
                                        {
                                            int x=query(1,1,n,a[i]+1,n);
                                            int c=1;
                                            if(query1(1,1,n,a[i]+1,n)==1e15)
                                            {

                                                c=i;
                                            }
                                            else
                                            {

                                                int p=query1(1,1,n,a[i]+1,n);


                                                c=i-p;
                                            }
                                      
                                            
                                            v[x].push_back({a[i],c});
                                        }
                                    }
                                    //cout<<ans<<endl;
                                    for(int i=0;i<=n;++i)
                                        v[i].clear();
                                    memset(tree1,0,sizeof(tree1));
                                    
                                    reverse(a+1,a+n+1);
                                    for(int i=1;i<=n;++i)
                                    {
                                        update(1,1,n,a[i],i);
                                    }
                                    
                                    
                                                                       
                                    for(int i=1;i<=n;++i)
                                    {                    
                                        update(1,1,n,a[i],1e15);                    
                                        for(int j=0;j<v[i].size();++j)
                                        {
                                            int num=v[i][j].first;
                                            int pos=v[i][j].second;
                                            if(query(1,1,n,num+1,n)==1e15)
                                            {
                                               
                                                ans+=(n-i+1)*num*pos;
                                            }
                                            else
                                            {
                                                int x=query(1,1,n,num+1,n);
                                               
                                                
                                                ans+=(x-i)*num*pos;
                                            }
                                        }
                                        update1(1,1,n,a[i],i);
                                        
                                        if(query(1,1,n,a[i]+1,n)==1e15)
                                            continue;
                                        else
                                        {
                                            int x=query(1,1,n,a[i]+1,n);
                                            int c=1;
                                            if(query1(1,1,n,a[i]+1,n)==1e15)
                                            {

                                                c=i;
                                            }
                                            else
                                            {

                                                int p=query1(1,1,n,a[i]+1,n);


                                                c=i-p;
                                            }
                                      
                                            
                                            v[x].push_back({a[i],c});
                                        }
                                    }
                                    cout<<ans;




                            }                       


Measured memory_bytes: 13696