#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define INF 1000000001
#define LINF 1000000000000000001
#define ll long long
#define ld long double
#define M 1000000007
#define E 0.0000001
#define N (1<<17)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define pld pair<long double, long double>
#define cll complex<long long>
#define cld complex<long double>
#define X real()
#define Y imag()
#define C 'a'
#define F first
#define S second
#define PI 3.1415926535897932384626433
using namespace std;
int c[N];
int f[N];
int main () {
int n;
cin>>n;
vector<pii> v;
for (int i = 1; i <= n; i++) {
int x;
cin>>x;
f[i - 1] = x;
v.push_back({x, i});
}
sort(v.rbegin(), v.rend());
int l = n;
int i;
ll ans = 0;
for (i = 1; l; i++) {
ll m = 0;
for (int j = 0; j < n; j++) {
int x = v[j].second;
if (c[x] || c[x - 1] == i || c[x + 1] == i) continue;
m = max((ll)v[j].first, m);
c[x] = i;
l--;
}
ans += m;
}
ll me = 0;
ll mo = 0;
for (int i = 0; i < n; i++) {
if (i % 2) {
me = max(me, f[i]);
} else mo = max(mo, f[i]);
}
if (ans < me + mo) {
cout<<ans<<" "<<i - 1<<endl;
for (int i = 1; i <= n; i++) cout<<c[i]<<" ";
cout<<endl;
} else {
cout<<me + mo<<" "<<2<<endl;
for (int i = 0; i < n; i++) cout<<(i % 2) + 1<<" ";
cout<<endl;
}
}