#include<bits/stdc++.h>
using namespace std;
const long long N=2e7+5,B=1e7,INF=1e18;
#define $ +B

long long n,a[N],pw[N];

struct abc{
	long long x,pos,val;
	abc(long long X=0,long long Y=0,long long Z=INF){
		x=X,pos=Y,val=Z;
	}
};
void getmin(abc &X,abc Y){
	if(Y.val<X.val) X=Y;
}
vector <abc> P[N],Q[N];

void dfs1(long long dep,long long ed,long long x,long long y,long long z,long long s){
	if(dep>ed){
		P[y-x $].push_back((abc){z-y $,s,z-x});
//		cout<<"P: "<<y-x<<" "<<z-y<<" "<<z-x<<endl;
		return ;
	}
	dfs1(dep+1,ed,x+a[dep],y,z,s);
	dfs1(dep+1,ed,x,y+a[dep],z,s+pw[dep]);
	dfs1(dep+1,ed,x,y,z+a[dep],s+2*pw[dep]);
}

void dfs2(long long dep,long long ed,long long x,long long y,long long z,long long s){
	if(dep>ed){
		Q[x-y $].push_back((abc){y-z $,s,z-x});
//		cout<<"Q: "<<x-y<<" "<<y-z<<" "<<z-x<<endl;
		return ;
	}
	dfs2(dep+1,ed,x+a[dep],y,z,s);
	dfs2(dep+1,ed,x,y+a[dep],z,s+pw[dep]);
	dfs2(dep+1,ed,x,y,z+a[dep],s+2*pw[dep]);
}

abc c[N]; 
long long lowbit(long long x){
	return x & (-x);
}
void modify(long long x,abc k){
	while(x<N) getmin(c[x],k),x+=lowbit(x);
}
abc query(long long x){
	abc tot;
	while(x) getmin(tot,c[x]),x-=lowbit(x);
	return tot;
}

int main(){
	pw[0]=1;
	for(long long i=1;i<=30;i++) pw[i]=pw[i-1]*3;
	cin>>n;
	for(long long i=1;i<=n;i++) cin>>a[i];
	long long m=n/2;
	dfs1(1,m,0,0,0,0);
	dfs2(m+1,n,0,0,0,0);
	
	abc ans;
	
	for(long long x=-B;x<=B;x++){
		for(long long i=0;i<(long long)Q[x $].size();i++) modify(Q[x $][i].x,Q[x $][i]);
		for(long long i=0;i<(long long)P[x $].size();i++){
			abc tot=query(P[x $][i].x);
			getmin(ans,(abc){0,P[x $][i].pos+tot.pos,P[x $][i].val+tot.val});
		}
	}
	
//	for(long long x=-B;x<=B;x++){
//		for(long long y=-B;y<=x;y++){
//			for(long long i=0;i<(long long)P[x $].size();i++){
//				for(long long j=0;j<(long long)Q[y $].size();j++){
//					if(P[x $][i].x>=Q[y $][j].x)
//						getmin(ans,(abc){0,P[x $][i].pos+Q[y $][j].pos,P[x $][i].val+Q[y $][j].val});
//				}
//			}
//		}
//	}
	
	cout<<ans.val<<endl;
	for(long long i=1;i<=n;i++) cout<<ans.pos/pw[i]%3+1<<" ";
}