#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;
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(){
	LL 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;
			}
		}
	}
	res+=mx;
	return id;
}
signed main(){
	srand(time(0));
	gi(n);
	LL now=0;
	for(int i=1;i<=n;i++)gi(a[i]),now=__gcd(now,a[i]); 
	sort(a+1,a+n+1);
	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();
		if(S[x].size()==1){
			len++;
			pp now=(*S[x].begin());
			S[x].erase(now);
			S[x].insert(pp(now.first,now.second-1));
			S[len].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);
			len++;
			if(fk2+now1.first>fk3+now2.first){
				S[len].insert(now1);
				S[x].erase(now1);
			}else{
				S[len].insert(now2);
				S[x].erase(now2);
			}
		}
		ans[i]=res;
	}
	for(int i=1;i<=n;i++)pi(ans[i],'\n');
	return 0;
} 
/*
*/