题解 数数

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define N 300010
#define ll long long
#define pb push_back
#define reg register int
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n;
ll a[N];

namespace force{
	int ans, k;
	vector< vector<int> > sta;
	void dfs(int u, int pos, vector<int> v, int sum) {
		v.pb(a[pos]);
		for (auto it:v) sum+=abs(a[pos]-it);
		if (u==k) {
			if (ans<sum) ans=sum, sta.clear(), sta.pb(v);
			else if (ans==sum) sta.pb(v);
			return ;
		}
		for (int i=pos+1; i<=n; ++i) {
			dfs(u+1, i, v, sum);
		}
	}
	void solve() {
		for (int i=1; i<=n; ++i) {
			ans=0; sta.clear(); k=i;
			for (int j=1; j<=n; ++j) dfs(1, j, vector<int>(), 0);
			printf("%d\n", ans);
			for (auto it:sta) {for (auto i:it) printf("%d ", i); printf("\n");}
			cout<<endl;
		}
		exit(0);
	}
}

namespace task1{
	vector<int> v;
	int val[N], sum, sta[N], top;
	void solve() {
		for (int i=1; i<=n; ++i) v.pb(a[i]);
		for (int j=0; j<v.size(); ++j)
			for (int k=j+1; k<v.size(); ++k)
				sum+=abs(v[j]-v[k]);
		sta[++top]=sum;
		for (int i=2; i<=n; ++i) {
			for (int j=0; j<v.size(); ++j) {
				val[j]=0;
				for (int k=0; k<v.size(); ++k) val[j]+=abs(v[j]-v[k]);
			}
			ll minn=INF, mini;
			for (int j=0; j<v.size(); ++j) {
				if (val[j]<minn) minn=val[j], mini=j;
			}
			sum-=minn;
			sta[++top]=sum;
			v.erase(v.begin()+mini);
		}
		while (top) {
			printf("%d\n", sta[top--]);
		}
		exit(0);
	}
}

namespace task2{
	int top;
	ll val[N], sum, sta[N], lst=INF;
	bool del[N];
	void solve() {
		ll t;
		for (reg j=1; j<=n; ++j)
			for (reg k=j+1; k<=n; ++k) {
				t=llabs(a[j]-a[k]);
				sum+=t; val[j]+=t; val[k]+=t;
			}
		sta[++top]=sum;
		for (reg i=2; i<=n; ++i) {
			//cout<<"i: "<<i<<endl;
			ll minn=INF, mini;
			for (reg j=1; j<=n; ++j) if (!del[j]) {
				//cout<<"j: "<<val[j]<<endl;
				if (lst!=INF) val[j]-=llabs(a[j]-lst);
				if (val[j]<minn) minn=val[j], mini=j;
			}
			sum-=minn;
			sta[++top]=sum;
			del[mini]=1; lst=a[mini];
		}
		while (top) {
			printf("%lld\n", sta[top--]);
		}
		exit(0);
	}
}

namespace task3{
	int top;
	ll b, c, sta[N];
	void solve() {
		for (int i=1; i<=n; ++i)
			if (a[i]) ++c;
			else ++b;
		sta[++top]=b*c;
		for (int i=2; i<=n; ++i) {
			if ((b-1)*c > b*(c-1)) --b;
			else --c;
			sta[++top]=b*c;
		}
		while (top) {
			printf("%lld\n", sta[top--]);
		}
		exit(0);
	}
}

namespace task{
	ll sum[N], ans;
	void solve() {
		sort(a+1, a+n+1);
		for (int i=1; i<=n; ++i) sum[i]=sum[i-1]+a[i];
		int pos1=0, pos2=n;
		for (int i=1; i<=n; ++i) {
			if (pos1 == n-pos2) {
				ans += sum[n]-sum[pos2]-a[pos2]*(n-pos2);
				ans += a[pos2]*pos1-sum[pos1];
				--pos2;
			}
			else {
				ans += sum[n]-sum[pos2]-a[pos1+1]*(n-pos2);
				ans += a[pos1+1]*pos1-sum[pos1];
				++pos1;
			}
			printf("%lld\n", ans);
		}
		exit(0);
	}
}

signed main()
{
	bool all01=1;
	n=read();
	for (int i=1; i<=n; ++i) {
		a[i]=read();
		if (a[i]!=0 && a[i]!=1) all01=0;
	}
	//force::solve();
	//if (all01) task3::solve();
	//else task2::solve();
	task::solve();
	
	return 0;
}