#include<cmath>
#include<cstdio>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<queue> 
#include<stack>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<random>
#include<ctime>
#include<unordered_map>
#include<unordered_set>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pp pair<LL,int>
#define LL long long
#define LD long double
#define ull unsigned long long
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		//return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
		return getchar();
	}
	template<class T> void gi(T& x){
		x=0; int f=1;char c=gc();
		if(c=='-')f=-1;
		for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
		x=x*f;
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void pi(T x,char c='\n'){
		if(x<0)pc('-'),x=-x;
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
using IO::pc;
const int mod=19260817;
inline int add(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
inline int dec(int x,int y){
	return x-y<0?x-y+mod:x-y;
}
int Qkpow(int a,int b){
	int ans=1,base=a;
	while(b){
		if(b&1)ans=1ll*ans*base%mod;
		base=1ll*base*base%mod;
		b>>=1;
	}
	return ans;
}
int fac[10000005],inv[10000005],Invn[10000005];
inline int binom(int n,int m){
	if(n<m||m<0)return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void init_C(int N){
	fac[0]=1;
	for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod; 
	inv[0]=1;
	inv[N]=Qkpow(fac[N],mod-2);
	for(int i=N-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	Invn[0]=Invn[1]=1;
	for(int i=2;i<=N;i++)Invn[i]=1ll*inv[i]*fac[i-1]%mod;
}
int n,len;
LL a[500005],ans[500005],res,mx;
set<pp>S[500005];
set<pp>::iterator it,it2;
LL getgcd(int x){
	LL gcd2=0;
	for(it2=S[x].begin();it2!=S[x].end();it2++)gcd2=__gcd((*it2).first,gcd2);
	return gcd2;
}
int split(){
	mx=-1;
	int id=0;
	for(int i=1;i<=len;i++){
		if(S[i].size()==1){
			if((*S[i].begin()).second==1)continue;
			else{
				if((*S[i].begin()).first>mx){
					mx=(*S[i].begin()).first;
					id=i;
				}
			}
		}else{
			LL fk=getgcd(i);
			it=S[i].end();
			it--;
			pp now1=(*it);
			it--;
			pp now2=(*it);
			S[i].erase(now1);
			LL fk2=getgcd(i);
			S[i].insert(now1);
			S[i].erase(now2);
			LL fk3=getgcd(i);
			S[i].insert(now2);
			if(max(fk2+now1.first,fk3+now2.first)-fk>=mx){
				mx=max(fk2+now1.first,fk3+now2.first)-fk;
				id=i;
			}
		}
	}
	return id;
}
void print(){
	cout<<len<<endl;
	for(int i=1;i<=len;i++){
		cout<<i<<":"<<endl;
		for(it2=S[i].begin();it2!=S[i].end();it2++){
			cout<<(*it2).first<<" "<<(*it2).second<<endl;
		}
		cout<<endl;
	}
}
unordered_map<LL,pp>H;
void Add(int x,int y){
	if(S[x].size()==1){
		pp now=(*S[x].begin());
		S[x].erase(now);
		S[x].insert(pp(now.first,now.second-1));
		S[y].insert(pp(now.first,1));
	}else{
		LL fk=getgcd(x);
		it=S[x].end();
		it--;
		pp now1=(*it);
		it--;
		pp now2=(*it);
		S[x].erase(now1);
		LL fk2=getgcd(x);
	 	S[x].insert(now1);
		S[x].erase(now2);
		LL fk3=getgcd(x);			
		S[x].insert(now2);
		if(fk2+now1.first>fk3+now2.first){
			S[y].insert(now1);
			S[x].erase(now1);
		}else{
			S[y].insert(now2);
			S[x].erase(now2);
		}
	}
}
signed main(){
	srand(time(0));
	gi(n);
	LL now=0,Sum=0;
	for(int i=1;i<=n;i++)gi(a[i]),now=__gcd(now,a[i]),Sum+=a[i]; 
	sort(a+1,a+n+1);
	/*
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(Sum-a[i]-a[j]+__gcd(a[i],a[j])==273){
				cout<<a[i]<<" "<<a[j]<<endl;
				exit(0);
			}
		}
	}
	*/
	len=1;
	for(int i=1;i<=n;i++){
		int r=i;
		while(r+1<=n&&a[r+1]==a[i])r++;
		S[1].insert(pp(a[i],r-i+1));
		i=r;
	} 
	res=ans[1]=now;
	for(int i=2;i<=n;i++){
		int x=split();
		len++;
		Add(x,len);
		res+=mx;
		H.clear();
		LL mn=1e18;
		for(int j=1;j<=len;j++){
			if(S[j].size()==1){
				LL X=(*S[j].begin()).first;
				if(H[X].first)H[X].second=j,mn=min(mn,X);
				else H[X].first=j;
			}
		}
		int id=split();
		if(mx>mn){
			res+=mx-mn;
			int id1=H[mn].first,id2=H[mn].second;
			int cs=(*S[id2].begin()).second;
			pp fk=*S[id1].begin();
			S[id1].clear(),S[id2].clear();
			S[id1].insert(pp(fk.first,fk.second+cs));
			Add(id,id2);
		}
		ans[i]=res;
	}
	for(int i=1;i<=n;i++)pi(ans[i],'\n');
	return 0;
} 
/*
15
22 15 21 22 16 27 10 15 17 14 26 23 30 12 18
*/