#include<bits/stdc++.h> #define int long long using namespace std; int n; int num[100010]; void readin(){ ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++)cin>>num[i]; } void solve(){ int ans=0; for(int i=1;i<=n;i++){ int mid=num[i]; ans+=i*i*mid; priority_queue<int>q1; priority_queue<int,vector<int>,greater<int> >q2; for(int j=i+1;j<=n;j++){ if(num[j]<mid){ q1.push(num[j]); }else{ q2.push(num[j]); } if((j-i)%2==0){ if(q1.size()<q2.size()){ q1.push(mid); mid=q2.top(); q2.pop(); }else if(q1.size()>q2.size()){ q2.push(mid); mid=q1.top(); q1.pop(); } ans+=i*j*mid; } } } cout<<ans; } signed main(){ readin(); solve(); return 0; }