#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;

int main()
{
   FAST/**/
   
   ll n;
   cin>>n;
   
   ll arr1[n];
   rep(n)
        cin>>arr1[i];
           
   pair<ll,ll> arr[n];
   rep(n)
        arr[i] = mp(arr1[i],i);
   sort(arr,arr+n);
   reverse(arr,arr+n);
   ll pos[n];
   rep(n)
        pos[i] = i;
   set<pair<ll,ll>> st;
   vector<ll> posi;
   rep(n)
        posi.pb(i);
   rep(n)
        st.insert(mp(arr[i].ff,arr[i].ss));
   ll ans = 0;        
   rep(n)
   {
       pair<ll,ll> ele;
       ll maxi = -inf;
       ll po = -1;
       bool cond = 0;
       ll pot = -1;
       autoit(st,it)
       {
           ll m1 = abs(posi[0]-it->ss)*it->ff;
           m1 = max(m1,abs(posi.back()-it->ss)*it->ff);
           if(m1>maxi)
           {
               maxi = m1;
               ele = *it;
               if(abs(posi.back()-it->ss)*it->ff == abs(posi[0]-it->ss)*it->ff)
                    cond = 1;
               else cond = 0;        
               if(m1 == abs(posi[0]-it->ss)*it->ff)
                    po = 0, pot = posi[0];
               else po = ((ll)posi.size()) - 1, pot = posi.back();       
           }
       }
       st.erase(ele);
       if(st.size() == 0)
       {
           ans+=maxi;
           break;
       }
       bool sig = 0;        
       if(cond)
       {
           maxi = -inf;
           po = -1;
           ll pot1 = -1;
           autoit(st,it)
           {
               ll m1 = abs(posi[0]-it->ss)*it->ff;
               m1 = max(m1,abs(posi.back()-it->ss)*it->ff);
               if(m1>maxi)
               {
                   maxi = m1;
                   ele = *it;
                   if(abs(posi.back()-it->ss)*it->ff == abs(posi[0]-it->ss)*it->ff)
                        cond = 1;
                   if(m1 == abs(posi[0]-it->ss)*it->ff)
                         pot1 = posi[0];
                   else pot1 = posi.back();        
               }
           }
           if(pot == pot1)
               po = ((ll)posi.size()) - 1 + 0 - po;
       }
       ans+=maxi;
       posi.erase(posi.begin()+po);
   }
   cout<<ans;
   
   return 0;        
}  
  
   