Efficient C++ Code :
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef
tree<
pair<int,int>,
null_type,
less<pair<int,int>>,
rb_tree_tag,
tree_order_statistics_node_update>
st;
typedef long long int ll ;
ll g5[500005],v[500005];
ll a [200005];
ll rr = -1e18 ;
unordered_map <ll,ll> b ;
unordered_map <ll,ll> kk ;
unordered_map <ll,ll> u ;
ll c[200000];
ll segtree[1000000];
void build(ll node,ll start,ll end)
{
if(start==end)
{
segtree[node] = 0 ;
c[start] = 0 ;
}
else
{
ll mid=(start+end)/2;
build(2*node,start,mid);
build(2*node+1,mid+1,end);
segtree[node]=segtree[2*node]+segtree[2*node+1];
}
}
ll query(ll node,ll start,ll end,ll l,ll r)
{
if(start>r || end<l)
{
return 0;
}
if(start>=l && end<=r)
{
return segtree[node];
}
ll mid=(start+end)/2;
ll left=query(node*2,start,mid,l,r);
ll right=query(node*2+1,mid+1,end,l,r);
return (left+right);
}
void update(ll node,ll start,ll end,ll ind,ll value)
{
if(start==end)
{
segtree[node]+=value;
c[ind]+=value;
}
else
{
ll mid=(start+end)/2;
if(ind<=mid)
{
update(2*node,start,mid,ind,value);
}
else
{
update(2*node+1,mid+1,end,ind,value);
}
segtree[node]=segtree[2*node] + segtree[2*node+1];
}
}
int main() {
ll n ;
cin>>n ; ll w = 0 ;
ll i = 1 ; vector <ll> r ;
while(i<=n){
cin>>a[i];w = w + a[i];
kk[a[i]]++;
r.push_back(a[i]);
i++;
}
sort(r.begin(),r.end()) ;
i = 0 ;
while(i<r.size()) {
b[r[i]] = i + 1 ;
i++;
}
st t ;
i = 1 ;
while(i<=n){
update(1,0,200000,b[a[i]],a[i]) ;
u[a[i]]++;
t.insert({a[i],u[a[i]]});
//cout<<a[i]<<" "<<u[a[i]];
//cout<<"\n";
if(i>=n/3){
ll count = i - n/3 ;
//cout<<i<<"\n";
//cout<<count<<"\n";
auto g = t.find_by_order(count-1);
pair <int,int> r = *g ;
//cout<<r.first<<" "<<r.second ;
//cout<<"\n";
ll ookk = r.first ;
ll sum = query(1,0,200000,0,b[r.first]-1);
sum = sum + r.first*r.second ;
g5[i] = sum ;
//cout<<i<<" ";cout<<g5[i]<<"\n";
}
i++;
}
//cout<<"\n";
u.clear();
build(1,0,200000);
t.clear();
ll c = 1 ;
i = n ;
while(i>=1){
update(1,0,200000,b[a[i]],a[i]) ;
u[a[i]]++;
t.insert({a[i],u[a[i]]});
//cout<<a[i]<<" "<<u[a[i]];
//cout<<"\n";
if(c>=n/3){
ll count = c - n/3 ;
//cout<<i<<"\n";
//cout<<count<<"\n";
auto g = t.find_by_order(c-count);
if(count!=0){
pair <int,int> r = *g ;
//cout<<r.first<<" "<<r.second ;
//cout<<"\n";
ll ookk = r.first ;
ll sum = query(1,0,200000,b[r.first]+1,200000);
//cout<<"\n";
//cout<<sum ;
//cout<<"\n";
sum = sum + r.first*(abs(r.second-kk[r.first]) + 1) ;
v[i] = sum ;
//cout<<i<<" ";cout<<v[i]<<"\n";
}
else
{
v[i] = 0 ;
//RM_RM!!!!!!!!!
//cout<<i<<" "<<v[i]<<"\n";
}
}
c++;
i--;
}
i = 1 ;
ll sum2 = a[1] ;
ll sum5 = w - a[1] ;
while(i<=n){
ll y2 = i ;
ll y5 = n - i ;
if(y2>=n/3 && y5>=n/3){
ll v2 = (sum2-g5[i]);
ll v5 = (sum5-v[i+1]);
//cout<<i<<" "<<g[i]<<" "<<v[i+1];
//cout<<"\n";
ll ans = v2 - v5 ;
//cout<<ans ;
//cout<<"\n";
rr = max(ans,rr);
}
sum2 = sum2 + a[i+1] ;
sum5 = w - sum2 ;
i++;
}
cout<<rr ;
return 0 ;
}