#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::pair<int, int>> inputVec;
std::vector<std::pair<int, int>> vec;
int n;

void swap1(int i){
    // always left >= right
    if(i <= 0) return;
    if(vec[i-1].first > vec[i].first && vec[i-1].second < 0) return;
    std::pair<int, int> tmp = vec[i-1];
    vec[i-1] = {vec[i].first, vec[i].second-1};
    vec[i] = {tmp.first, tmp.second+1};
    swap1(i-1);
}

void swap2(int i){
    if(i >= n-1) return;
    if(vec[i-1].first < vec[i].first && vec[i+1].second > 0) return;
    std::pair<int, int> tmp = vec[i+1];
    vec[i+1] = {vec[i].first, vec[i].second+1};
    vec[i] = {tmp.first, tmp.second-1};
    swap2(i+1);
}

int main(){
    std::cin >> n;
    for(int i = 0; i < n; i++){
        int a;
        std::cin >> a;
        inputVec.push_back({a, i});

    }
    std::sort(inputVec.begin(), inputVec.end(), std::greater<>());
    for(int i = 0; i < n; i++){
        vec.push_back({inputVec[i].first, i - inputVec[i].second});
    }
    for(int i = 1; i < n; i++){
        swap1(i);
    }
    long long ans1 = 0;
    for(auto item : vec){
        ans1 += long(item.first)*long(std::abs(item.second));
    }
    std::reverse(inputVec.begin(), inputVec.end());
    for(int i = 0; i < n; i++){
        vec[i] = {inputVec[i].first, i - inputVec[i].second};
    }
    for(int i = n-2; i >= 0; i--){
        swap2(i);
    }
    long long ans2 = 0;
    for(auto item : vec){
        ans2 += long(item.first)*long(std::abs(item.second));
    }
    std::cout << std::max(ans1, ans2) << std::endl;
}
