stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#define pb push_back

using namespace std;

const int N=2100;

priority_queue<int> Q;

vector<int> E[N],W[N];

int n,a[N],d[N],vis[N];

void dfs(int x)

{

	vis[x]=1;

	for(auto R:E[x]) if(!vis[R]) W[x].pb(R);

	for(auto R:E[x]) if(!vis[R]) dfs(R);

}

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++) cin>>a[i];

	sort(a+1,a+n+1);

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

			if(__gcd(a[i],a[j])>1) E[i].pb(j),E[j].pb(i);

	for(int i=1;i<=n;i++) sort(E[i].begin(),E[i].end());

	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);

	for(int i=1;i<=n;i++) for(auto R:W[i]) d[R]++;

	for(int i=1;i<=n;i++) if(!d[i]) Q.push(i);

	while(!Q.empty())

	{

		int x=Q.top();Q.pop();

		printf("%d ",a[x]);

		for(auto R:W[x])

			if(--d[R]==0) Q.push(R);

	}

}


// Faster C++ solution for the same problem (measured speedup: 1.1223142551860854x):
#include<cstdio>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const int N=2333;

int a[N];

int g[N][N];

int n;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

struct sumireko{int to,ne;}e[N*1000];

int he[N],ecnt;

void addline(int f,int t)

{

	e[++ecnt].to=t;

	e[ecnt].ne=he[f];

	he[f]=ecnt;

}



bool vv[N];

int bi;

int sp[N];

vector<int> to[N];

void dfs(int x)

{

	vv[x]=1;

	for(int i=he[x],t;i;i=e[i].ne)

	{

		t=e[i].to;

		if(!vv[t])

		{

			to[x].push_back(t);

			dfs(t);

		}

	}

}



priority_queue<int> q;



int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	sort(a+1,a+1+n);

	for(int i=n;i;i--)

		for(int j=i-1;j;j--)

			if(gcd(a[i],a[j])!=1)

				addline(i,j),addline(j,i)/*,printf("line %d %d\n",i,j)*/;

	for(int i=1;i<=n;i++) if(!vv[i])

	{

		bi++;

		sp[bi]=i;

		dfs(i);

	}

	/*printf("%d\n",bi);

	for(int i=1;i<=bi;i++) printf("%d ",sp[i]);

	puts("\n----------------------------------");

	for(int i=1;i<=n;i++)

	{

		printf("%d:",i);

		for(int j=0;j<to[i].size();j++) printf("%d ",to[i][j]);

		putchar('\n');

	}

	puts("\n----------------------------------");*/

	for(int i=1;i<=bi;i++)

		q.push(sp[i]);

	while(!q.empty())

	{

		int g=q.top();

		q.pop();

		printf("%d ",a[g]);

		for(int i=0;i<to[g].size();i++) q.push(to[g][i]);

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define mp make_pair

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef vector<int > vi;

typedef pair<int ,int > pii;

typedef vector<pii> vii;

const int inf=0x3f3f3f3f, maxn=100007, mod=1e9+7;

const ll linf=0x3f3f3f3f3f3f3f3fLL;

int n,a[2007];

vi e[2007];

vi e2[2007];

bool vis[2007];

int deg[2007];

void dfs(int x){

	if(vis[x])return ;

	vis[x]=true;

	for(int i=0;i<e[x].size();i++){

		if(!vis[e[x][i]]){

			e2[x].pb(e[x][i]);

			deg[e[x][i]]++;

			dfs(e[x][i]);

		}

	}

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	sort(a+1,a+n+1);

	for(int i=1;i<=n;i++){

		for(int j=i+1;j<=n;j++){

			if(__gcd(a[i],a[j])>1)e[i].pb(j),e[j].pb(i);

		}

	}

	for(int i=1;i<=n;i++)sort(e[i].begin(),e[i].end());

	for(int i=1;i<=n;i++)if(!vis[i])dfs(i);

	memset(vis,0,sizeof(vis));

	for(int i=1;i<=n;i++){

		for(int j=n;j>=1;j--){

			if(!deg[j]&&!vis[j]){

				vis[j]=true;

				printf("%d ",a[j]);

				for(int k=0;k<e2[j].size();k++)deg[e2[j][k]]--;

				break;

			}

		}

	}

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1014994043772155x):
// =================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// =================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

#define re register

using namespace std;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=2000+10;



struct Edge { int v,nxt; } e[N];

int head[N];



inline void addEdge(int u,int v) {

    static int cnt=0;

    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;

}



int n;

int a[N],vis[N],deg[N];

int G[N][N];



inline void dfs(int u) {

    vis[u]=1;

    for (re int i=1;i<=n;++i) {

        if (vis[i]||!G[u][i]) continue;

        ++deg[i],addEdge(u,i);

        dfs(i);

    }

}



inline void topsort() {

    priority_queue<int> Q;

    for (re int i=1;i<=n;++i)

        if (!deg[i]) Q.push(i);

    while (!Q.empty()) {

        int u=Q.top(); Q.pop();

        printf("%d ",a[u]);

        for (re int i=head[u];i;i=e[i].nxt) Q.push(e[i].v);

    }

}



int main() {

    n=read();

    for (re int i=1;i<=n;++i) a[i]=read();

    sort(a+1,a+n+1);

    for (re int i=1;i<=n;++i)

        for (re int j=i+1;j<=n;++j) {

            if (__gcd(a[i],a[j])==1) continue;

            G[i][j]=G[j][i]=1;

        }

    for (re int i=1;i<=n;++i)

        if (!vis[i]) dfs(i);

    topsort();

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<int, int> PII;



const int MM = 1e9 + 7;

const double eps = 1e-8;

const int MAXN = 2e6 + 10;



int n, m;



void prework(){



}



void read(){



}



class BITree{

public:

    static const int SIZE = 100010, BIAS = 5;

    long long u[SIZE];

    void clear(){

        memset(u,0,sizeof(u));

    }

    void modify(int x, long long v){

        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]+=v;

    }

    long long getsum(int x){

        long long s=0;

        for(x+=BIAS;x;x-=x&-x) s+=u[x];

        return s;

    }

} hnk;



int a[MAXN];

int f[MAXN];

ll g[MAXN];



void solve(int casi){

	scanf("%d", &n);

	map<int, int> nico;

	for(int i = 1; i <= n; i++){

		scanf("%d", &a[i]);

		nico[a[i]] = 1;

	}

	int cnt = 0;

	for(auto &x : nico){

		x.second = ++cnt;

	}

	

//	for(auto &x : nico){

//		cout<<x.first<<' '<<x.second<<endl;

//	}

	

	hnk.clear();

	for(int i = 1; i <= n; i++){

		hnk.modify(1, 1);

		hnk.modify(nico[a[i]] + 1, -1);

	}

	cnt = 0;

	for(auto &x : nico){

		++cnt;

		f[cnt] = x.first;

		g[cnt] = hnk.getsum(x.second);

	}

	f[0] = 0;

	/*

	for(int i = 1; i <= cnt; i++){

		cout<<f[i]<<' ';

	} cout<<endl;

	for(int i = 1; i <= cnt; i++){

		cout<<g[i]<<' ';

	} cout<<endl;

	*/for(int i = 1, j = 1; i <= n; i++){

		ll ans = 0;

		while(j <= cnt && a[i] >= f[j]){

			ans += g[j] * (f[j] - f[j-1]);

			j++;

		}

		printf("%lld\n", ans);

	}

}



void printans(){



}





int main(){

	prework();

	int T = 1;

//	cin>>T;

	for(int i = 1; i <= T; i++){

		read();

		solve(i);

		printans();

	}

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 9.431240515186325x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define MN 100005

using namespace std;

inline int in(){

    int x=0;bool f=0; char c;

    for (;(c=getchar())<'0'||c>'9';f=c=='-');

    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}

int st[MN],sum[MN],a[MN],b[MN],pos[MN],dif[MN];

int n,top,mx,cnt,cur;

ll res,ans[MN];

int main()

{

	n=in();top=0;st[top]=0;

	for (int i=1;i<=n;++i) a[i]=b[i]=in();b[n+1]=0x7fffffff;

	for (int i=1;i<=n;++i) if (!top||a[i]>a[st[top]]) st[++top]=i;

	sort(b+1,b+n+1);cnt=unique(b+1,b+n+1)-b-1;b[cnt+1]=0x7fffffff;

	for (int i=1;i<=n;++i) pos[i]=lower_bound(b+1,b+cnt+1,a[i])-b,++sum[pos[i]],mx=max(mx,pos[i]);

	for (int i=1;i<=cnt;++i) dif[i]=b[i]-b[i-1];

	for (int i=mx;i>=0;--i){

		sum[i]+=sum[i+1];res=1ll*dif[i]*sum[i];

		if (pos[st[top]]==i) cur=st[top],--top;ans[cur]+=res;

	}ans[1]+=ans[0]; 

	for (int i=1;i<=n;++i) printf("%lld\n",ans[i]);return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<int, int> PII;



const int MM = 1e9 + 7;

const double eps = 1e-8;

const int MAXN = 2e6 + 10;



int n, m;



void prework(){



}



void read(){



}



class BITree{

public:

    static const int SIZE = 100010, BIAS = 5;

    long long u[SIZE];

    void clear(){

        memset(u,0,sizeof(u));

    }

    void modify(int x, long long v){

        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]+=v;

    }

    long long getsum(int x){

        long long s=0;

        for(x+=BIAS;x;x-=x&-x) s+=u[x];

        return s;

    }

} hnk;



int a[MAXN];

int f[MAXN];

ll g[MAXN];



void solve(int casi){

	scanf("%d", &n);

	map<int, int> nico;

	for(int i = 1; i <= n; i++){

		scanf("%d", &a[i]);

		nico[a[i]] = 1;

	}

	int cnt = 0;

	for(auto &x : nico){

		x.second = ++cnt;

	}

	

//	for(auto &x : nico){

//		cout<<x.first<<' '<<x.second<<endl;

//	}

	

	hnk.clear();

	for(int i = 1; i <= n; i++){

		hnk.modify(1, 1);

		hnk.modify(nico[a[i]] + 1, -1);

	}

	cnt = 0;

	for(auto &x : nico){

		++cnt;

		f[cnt] = x.first;

		g[cnt] = hnk.getsum(x.second);

	}

	f[0] = 0;

	/*

	for(int i = 1; i <= cnt; i++){

		cout<<f[i]<<' ';

	} cout<<endl;

	for(int i = 1; i <= cnt; i++){

		cout<<g[i]<<' ';

	} cout<<endl;

	*/for(int i = 1, j = 1; i <= n; i++){

		ll ans = 0;

		while(j <= cnt && a[i] >= f[j]){

			ans += g[j] * (f[j] - f[j-1]);

			j++;

		}

		printf("%lld\n", ans);

	}

}



void printans(){



}





int main(){

	prework();

	int T = 1;

//	cin>>T;

	for(int i = 1; i <= T; i++){

		read();

		solve(i);

		printans();

	}

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.7689032153588367x):
#include<iostream>

#include<stdio.h>

#include<vector>

#include<cmath>

#include<queue>

#include<string.h>

#include<map>

#include<set>

#include<algorithm>

#define ll long long

#define pi pair < ll,ll >

#define mp(a,b) make_pair(a,b)

#define rep(i,a,b) for(int i = a;i < b;i++)

#define N 300004

#define INF 1e9+7



using namespace std;



ll n,freq[N];

pi ar[N];

set < pi > s;

ll cnt = 1;



int main()

{

    ios_base::sync_with_stdio(false);



    cin >> n;



    rep(i,0,n)

    {

        cin >> ar[i].first;

        ar[i].first *= -1;

        ar[i].second=i;

        s.insert(ar[i]);

    }



    while(s.size() != 1)

    {

        pi cur = *(s.begin());



       //cout << -cur.first << " " << cur.second << " " << cnt << endl;



        s.erase(s.begin());



        if((*s.begin()).first == cur.first)

        {

            s.erase(s.begin());

            cnt++;

            s.insert(cur);

        }

        else

        {

         //   cout << "here " << cnt*(-cur.first + (*s.begin()).first)<<"\n";

            freq[cur.second] += cnt*(-cur.first+(*s.begin()).first);

            cur.first = (*s.begin()).first;

            s.insert(cur);

        }

    }



    freq[0] -= cnt*(*s.begin()).first;



    rep(i,0,n)

        cout << freq[i] << "\n";



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define name ""

#define ini freopen(name".inp","r",stdin); freopen(name".out","w",stdout)

#define foe(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); it++)

#define long long long 

#define db double 

#define pii pair <int, int>

#define pll pair <long, long>

#define all(c) c.begin(), c.end()

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)



const int INF = 1e9+7;

const int MOD = 1e9+7;

const int dx[4] = {0,0,-1,1};

const int dy[4] = {-1,1,0,0};



const int N = 1e5+1;



int n, a[N], val[N], b[N];

long res[N];

vector <int> pos[N];



int main()

{

	fastio;

	cin >> n;

	for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

	sort(a + 1, a + 1 + n);

	for (int i = 1; i <= n; i++){

		int x = lower_bound(a + 1, a + 1 + n, b[i]) - a;

		val[x] = b[i];

		pos[x].push_back(i);

	}

	int pre = -INF, x = INF;

	long cnt = 0;

	for (int i = n; i >= 0; i--){

		if (i == 0){

			res[x] += cnt * pre;

			break;

		}

		if (pos[i].size() == 0) continue;

		if (pre == -INF){

			x = pos[i][0];

			pre = val[i];

			cnt += pos[i].size();

		}	

		else {

			res[x] += cnt * (pre - val[i]);

			if (pos[i][0] < x) x = pos[i][0];

			cnt += pos[i].size();

			pre = val[i];

		}

	}

	for (int i = 1; i <= n; i++) cout << res[i] << '\n';

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5040182062553056x):
/*input

10

1 2 1 3 2 4 2 5 8 1

*/



#include <iostream>

#include <vector>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <string>

#include <cassert>

#include <algorithm>

#include <cstdlib>

#include <numeric>

#include <utility>

#include <tuple>

#include <climits>

#include <fstream>

#include <bitset>

#include <map>

#include <unordered_map>

#include <set>

#include <unordered_set>

#include <stack>

#include <queue>

#include <random>

#include <chrono>

#include <ios>

#include <iomanip>

#include <functional>

#include <array>



using namespace std;



#define FOR(i, a, b) for (int i = a; i <= b; ++i)

#define FORA(i, a) for (auto &i : a)

#define FORB(i, a, b) for (int i = a; i >= b; --i)

#define SZ(a) ((int) a.size())

#define ALL(a) begin(a), end(a)



typedef int64_t ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

typedef vector<int> vi;

typedef vector<ll> vl;

#define fi first

#define se second



// start of code



int32_t main()

{

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);



	int N;

	cin >> N;

	vector<pii> vec(N + 1);

	vec[0] = pii(0, 0);

	FOR(i, 1, N) {

		cin >> vec[i].fi;

		vec[i].se = i;

	}



	sort(ALL(vec));

	vl ans(N + 1);

	FOR(i, 1, N) {

		ans[vec[i].se] = (ll) (vec[i].fi - vec[i - 1].fi) * (N - i + 1);

	}



	int curMin = N + 1;

	FORB(i, N, 1) {

		curMin = min(curMin, vec[i].se);

		if (curMin != vec[i].se) {

			ans[curMin] += ans[vec[i].se];

			ans[vec[i].se] = 0;

		}

	}

	FOR(i, 1, N) cout << ans[i] << '\n';

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<int, int> PII;



const int MM = 1e9 + 7;

const double eps = 1e-8;

const int MAXN = 2e6 + 10;



int n, m;



void prework(){



}



void read(){



}



class BITree{

public:

    static const int SIZE = 100010, BIAS = 5;

    long long u[SIZE];

    void clear(){

        memset(u,0,sizeof(u));

    }

    void modify(int x, long long v){

        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]+=v;

    }

    long long getsum(int x){

        long long s=0;

        for(x+=BIAS;x;x-=x&-x) s+=u[x];

        return s;

    }

} hnk;



int a[MAXN];

int f[MAXN];

ll g[MAXN];



void solve(int casi){

	scanf("%d", &n);

	map<int, int> nico;

	for(int i = 1; i <= n; i++){

		scanf("%d", &a[i]);

		nico[a[i]] = 1;

	}

	int cnt = 0;

	for(auto &x : nico){

		x.second = ++cnt;

	}

	

//	for(auto &x : nico){

//		cout<<x.first<<' '<<x.second<<endl;

//	}

	

	hnk.clear();

	for(int i = 1; i <= n; i++){

		hnk.modify(1, 1);

		hnk.modify(nico[a[i]] + 1, -1);

	}

	cnt = 0;

	for(auto &x : nico){

		++cnt;

		f[cnt] = x.first;

		g[cnt] = hnk.getsum(x.second);

	}

	f[0] = 0;

	/*

	for(int i = 1; i <= cnt; i++){

		cout<<f[i]<<' ';

	} cout<<endl;

	for(int i = 1; i <= cnt; i++){

		cout<<g[i]<<' ';

	} cout<<endl;

	*/for(int i = 1, j = 1; i <= n; i++){

		ll ans = 0;

		while(j <= cnt && a[i] >= f[j]){

			ans += g[j] * (f[j] - f[j-1]);

			j++;

		}

		printf("%lld\n", ans);

	}

}



void printans(){



}





int main(){

	prework();

	int T = 1;

//	cin>>T;

	for(int i = 1; i <= T; i++){

		read();

		solve(i);

		printans();

	}

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.7906875878985453x):
#include <bits/stdc++.h>

#define ll long long

#define maxn 100001

using namespace std;

ll a[maxn], id[maxn], n;

map<ll, ll> trace, b;

int main()

{

    cin >> n;

    for (int i = 1; i <= n; i++)

    {

        cin >> a[i];

        if (b[a[i]] == 0)

            b[a[i]] = i;

        trace[a[i]]++;

    }

    trace[0] = 0;



    ll pos = n + 1, x = 0, y = 0;

    for (auto i = trace.end(); i != trace.begin(); i--)

    {



        if (i != trace.end())

        {



            id[pos] += (x - i->first) * y;

            x = i->first;

            pos = min(b[x], pos);

            y += i->second;

        }

    }

    id[pos] += (x - 0) * y;

    for (int i = 1; i <= n; i++)

        cout << id[i] << endl;

}

/*

10

1 2 1 3 2 4 2 5 8 1

*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define name ""

#define ini freopen(name".inp","r",stdin); freopen(name".out","w",stdout)

#define foe(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); it++)

#define long long long 

#define db double 

#define pii pair <int, int>

#define pll pair <long, long>

#define all(c) c.begin(), c.end()

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)



const int INF = 1e9+7;

const int MOD = 1e9+7;

const int dx[4] = {0,0,-1,1};

const int dy[4] = {-1,1,0,0};



const int N = 1e5+1;



int n, a[N], val[N], b[N];

long res[N];

vector <int> pos[N];



int main()

{

	fastio;

	cin >> n;

	for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

	sort(a + 1, a + 1 + n);

	for (int i = 1; i <= n; i++){

		int x = lower_bound(a + 1, a + 1 + n, b[i]) - a;

		val[x] = b[i];

		pos[x].push_back(i);

	}

	int pre = -INF, x = INF;

	long cnt = 0;

	for (int i = n; i >= 0; i--){

		if (i == 0){

			res[x] += cnt * pre;

			break;

		}

		if (pos[i].size() == 0) continue;

		if (pre == -INF){

			x = pos[i][0];

			pre = val[i];

			cnt += pos[i].size();

		}	

		else {

			res[x] += cnt * (pre - val[i]);

			if (pos[i][0] < x) x = pos[i][0];

			cnt += pos[i].size();

			pre = val[i];

		}

	}

	for (int i = 1; i <= n; i++) cout << res[i] << '\n';

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.530993596381987x):
#include <bits/stdc++.h>

#define ll long long

#define maxn 100001

using namespace std;

ll a[maxn], id[maxn], n;

map<ll, ll> trace, b;

int main()

{

    cin >> n;

    for (int i = 1; i <= n; i++)

    {

        cin >> a[i];

        if (b[a[i]] == 0)

            b[a[i]] = i;

        trace[a[i]]++;

    }

    trace[0] = 0;



    ll pos = n + 1, x = 0, y = 0;

    for (auto i = trace.end(); i != trace.begin(); i--)

    {



        if (i != trace.end())

        {



            id[pos] += (x - i->first) * y;

            x = i->first;

            pos = min(b[x], pos);

            y += i->second;

        }

    }

    id[pos] += (x - 0) * y;

    for (int i = 1; i <= n; i++)

        cout << id[i] << endl;

}

/*

10

1 2 1 3 2 4 2 5 8 1

*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define name ""

#define ini freopen(name".inp","r",stdin); freopen(name".out","w",stdout)

#define foe(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); it++)

#define long long long 

#define db double 

#define pii pair <int, int>

#define pll pair <long, long>

#define all(c) c.begin(), c.end()

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)



const int INF = 1e9+7;

const int MOD = 1e9+7;

const int dx[4] = {0,0,-1,1};

const int dy[4] = {-1,1,0,0};



const int N = 1e5+1;



int n, a[N], val[N], b[N];

long res[N];

vector <int> pos[N];



int main()

{

	fastio;

	cin >> n;

	for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

	sort(a + 1, a + 1 + n);

	for (int i = 1; i <= n; i++){

		int x = lower_bound(a + 1, a + 1 + n, b[i]) - a;

		val[x] = b[i];

		pos[x].push_back(i);

	}

	int pre = -INF, x = INF;

	long cnt = 0;

	for (int i = n; i >= 0; i--){

		if (i == 0){

			res[x] += cnt * pre;

			break;

		}

		if (pos[i].size() == 0) continue;

		if (pre == -INF){

			x = pos[i][0];

			pre = val[i];

			cnt += pos[i].size();

		}	

		else {

			res[x] += cnt * (pre - val[i]);

			if (pos[i][0] < x) x = pos[i][0];

			cnt += pos[i].size();

			pre = val[i];

		}

	}

	for (int i = 1; i <= n; i++) cout << res[i] << '\n';

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.344178367040412x):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using namespace std;

#define ll long long int

#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >

//added two more functions to set

//(1)*(set.find_by_order(k))[kth element in the sorted set] 

//(2)set.order_of_key(k)[count of elements strictly less than k]

typedef vector< int > vi;

typedef vector< ll > lvi;

typedef vector< vi > vvi;

typedef vector< lvi > lvvi;

typedef pair< int,int > ii;

typedef pair< ll,ll > lii;

#define sz(a) int((a).size())

#define pb push_back

#define all(c) (c).begin(),(c).end()

#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator

#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps

#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors

#define tc(t) int (t); cin>>(t);while((t)--)

#define ff first

#define ss second

#define mp make_pair

#define ld long double

#define ull unsigned long long int

#define mod 1000000007

int main()

{

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);	

	ll n,a[200000];

	cin>>n;

	map<ll,lii> mp1;

	for(int i=0;i<n;i++)

	{

		cin>>a[i];

	}

	for(ll i=n-1;i>=0;i--)

	{

		mp1[a[i]].ff=i;

		mp1[a[i]].ss++;

	}

	ll pos=n;

	lvi ans(n+2,0);

	ll ct=0;

	mp1[0]={-1,0};

	for(auto it=mp1.crbegin();it!=mp1.crend();it++)

	{

		pos=min(pos,it->ss.ff);

		if(pos==-1) break;

		ct+=it->ss.ss;

		ll value=it->ff;

		it++;

		ll next=it->ff;

		ll dif=value-next;

		ans[pos]+=(dif*ct);

		it--;

	}

	for(int i=0;i<n;i++)

	{

		cout<<ans[i]<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<int, int> PII;



const int MM = 1e9 + 7;

const double eps = 1e-8;

const int MAXN = 2e6 + 10;



int n, m;



void prework(){



}



void read(){



}



class BITree{

public:

    static const int SIZE = 100010, BIAS = 5;

    long long u[SIZE];

    void clear(){

        memset(u,0,sizeof(u));

    }

    void modify(int x, long long v){

        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]+=v;

    }

    long long getsum(int x){

        long long s=0;

        for(x+=BIAS;x;x-=x&-x) s+=u[x];

        return s;

    }

} hnk;



int a[MAXN];

int f[MAXN];

ll g[MAXN];



void solve(int casi){

	scanf("%d", &n);

	map<int, int> nico;

	for(int i = 1; i <= n; i++){

		scanf("%d", &a[i]);

		nico[a[i]] = 1;

	}

	int cnt = 0;

	for(auto &x : nico){

		x.second = ++cnt;

	}

	

//	for(auto &x : nico){

//		cout<<x.first<<' '<<x.second<<endl;

//	}

	

	hnk.clear();

	for(int i = 1; i <= n; i++){

		hnk.modify(1, 1);

		hnk.modify(nico[a[i]] + 1, -1);

	}

	cnt = 0;

	for(auto &x : nico){

		++cnt;

		f[cnt] = x.first;

		g[cnt] = hnk.getsum(x.second);

	}

	f[0] = 0;

	/*

	for(int i = 1; i <= cnt; i++){

		cout<<f[i]<<' ';

	} cout<<endl;

	for(int i = 1; i <= cnt; i++){

		cout<<g[i]<<' ';

	} cout<<endl;

	*/for(int i = 1, j = 1; i <= n; i++){

		ll ans = 0;

		while(j <= cnt && a[i] >= f[j]){

			ans += g[j] * (f[j] - f[j-1]);

			j++;

		}

		printf("%lld\n", ans);

	}

}



void printans(){



}





int main(){

	prework();

	int T = 1;

//	cin>>T;

	for(int i = 1; i <= T; i++){

		read();

		solve(i);

		printans();

	}

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.82192149021836x):
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

int a[100005];

LL ans[100005];

pii p[100005];

int main(){

    int n;

    scanf("%d", &n);

    for(int i=1;i<=n;i++){

        scanf("%d", &a[i]);

        p[i] = pii(a[i], -i);

    }

    p[n+1] = pii(0, 0);

    sort(p+1, p+1+n);

    reverse(p+1, p+1+n);



    int mn = 1e9;

    for(int i=1;i<=n;i++){

        mn = min(mn, -p[i].second);

        if(a[-p[i].second] != a[-p[i+1].second]){

            int d = a[-p[i].second]-a[-p[i+1].second];

            ans[mn] += d*1ll*i;

        }

    }

    for(int i=1;i<=n;i++) printf("%lld\n", ans[i]);

}