#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//long long int countt[200003];
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define int long long
#define endl "\n"
const int mod=1e9+7;
signed main()
{
    FAST;
    
    int i=0,j=0,k=0,n=0,m=0,count=0,temp=0;
    int temp1=0,temp2=0,temp3=0,x=0,l=0,y=0,sum=0;
    int left=0,up=0,anss=0,start=0,end=0,r=0,qq=0,total=0;
    int maxx=0,minn=0,curr=0,ans=0,places=0,zeroes=0,low=0,high=0;
    int prev=0,mid=0,z=0,d=0,val=0,pos=0,shift=0,h=0,right=0,var=0;
    int reqd=0,lef=0;
    
    cin>>n;
    vector<pair<int,int>> a(n);
    map<int,int> mp;
    set<int> st;
    for(i=0;i<n;i++)
    {
        cin>>a[i].first;
        a[i].second=i;
        mp[a[i].first]++;
        st.insert(i);
    }
    
    for(auto it: mp)
    {
        if(it.second>1)
        {
            ans=1;
        }
    }
    sort(a.begin(),a.end() , greater<pair<int,int>>());
    
    for(i=0;i<n;i++)
    {
        //cout<<ans<<endl;
        left = abs(a[i].second-*st.begin());
        auto it1 = st.begin();
        auto it = st.end();
        it--;
        right = abs(a[i].second - *it);
        
        if(left>right)
        {
            ans+=(a[i].first*left);
            st.erase(it1);
        }
        
        else if(right>left)
        {
            ans+=(a[i].first*right);
            st.erase(it);
        }
        
        else
        {
            if(i+1<n)
            {
                if(a[i+1].second<a[i].second)
                {
                    ans+=(a[i].first*left);
                    st.erase(it1);
                }
                
                else
                {
                    ans+=(a[i].first*right);
                    st.erase(it);
                    
                }
            }
            
            else
            {
                ans+=(a[i].first*left);
            }
        }
        
    }
    
    cout<<ans<<endl;
    
}