4.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct BIT {
    int n; vector<ll> bit;
    BIT(int n): n(n), bit(n + 1) {}
    void update(int i, ll v) {
        for (; i <= n; i += i & -i) {
            bit[i] += v;
        }
    }
    ll get(int i) {
        ll v = 0;
        for (; i; i -= i & -i) {
            v += bit[i];
        }
        return v;
    }
    void reset() {
        for (int i = 1; i <= n; i++) {
            bit[i] = 0;
        }
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r")) freopen("in", "r", stdin);
    int n; cin >> n;
    // ll sum = 0;
    vector<int> a(n + 1);
    vector<int> vec;
    for (int i = 1; i <= n; i++) {
        // sum += a[i];
        cin >> a[i];
        vec.push_back(a[i]);
    }
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    vector<int> b(n + 1);
    for (int i = 1; i <= n; i++) {
        b[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
    }
    BIT Cnt(vec.size()), Sum(vec.size());
    vector<ll> sumL(n + 1);
    ll curSum = 0;
    for (int i = 1; i <= n; i++) {
        curSum += a[i];
        sumL[i] = curSum + Cnt.get(b[i]) * a[i] - Sum.get(b[i]);
        // cout << "i = " << i << '\n';
        // cout << "curSum = " << curSum << '\n';
        // cout << "Cnt.get(b[i]) = " << Cnt.get(b[i]) << '\n';
        // cout << "Sum.get(b[i]) = " << Sum.get(b[i]) << '\n';
        // cout << "sumL[i] = " << sumL[i] << '\n';
        // cout << - Sum.get(b[i]) * Cnt.get(b[i]) << '\n';
        // cout << '\n';
        Cnt.update(1, 1);
        Sum.update(1, a[i]);
        Cnt.update(b[i] + 1, - 1);
        Sum.update(b[i] + 1, - a[i]);
    }
    Cnt.reset();
    Sum.reset();
    vector<ll> sumR(n + 1);
    curSum = 0;
    for (int i = n; i >= 1; i--) {
        curSum += a[i];
        sumR[i] = curSum + Cnt.get(b[i]) * a[i] - Sum.get(b[i]);
        // cout << "i = " << i << '\n';
        // cout << "curSum = " << curSum << '\n';
        // cout << "Cnt.get(b[i]) = " << Cnt.get(b[i]) << '\n';
        // cout << "Sum.get(b[i]) = " << Sum.get(b[i]) << '\n';
        // cout << "sumR[i] = " << sumR[i] << '\n';
        // cout << - Sum.get(b[i]) * Cnt.get(b[i]) << '\n';
        // cout << '\n';
        Cnt.update(1, 1);
        Sum.update(1, a[i]);
        Cnt.update(b[i] + 1, - 1);
        Sum.update(b[i] + 1, - a[i]);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, sumL[i] + sumR[i] - a[i]);
    }
    cout << ans << '\n';
}