import java.util.Scanner;
import java.util.*;
//import java.util.Arrays;
import java.util.ArrayList;
public class maalarit {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int fenceCount = scanner.nextInt();
int painters = 1;
int actualPainters = 1;
int[] paintedBy = new int[fenceCount];
int[][] fences = new int[fenceCount][3];
//TreeSet<Integer, Integer> t = new TreeSet<Integer, Integer>();
for (int i = 0; i < fenceCount; i++) {
// t.add(scanner.nextInt(), i);
fences[i][0] = scanner.nextInt();
fences[i][1] = i;
}
//Arrays.sort(fences, new ColumnComparator(0));
Arrays.sort(fences, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o2[0], o1[0]);
}
});
for (int i = 0; i < fenceCount; i++) {
//if (i == 0 || t.get(
}
boolean b = false;
int sum = 0;
for (int[] i : fences) {
//System.out.println( (i[1] + 1 == fenceCount ));
if ((i[1] == 0 || paintedBy[i[1]-1] != painters) &&
(i[1] + 1 == fenceCount || paintedBy[i[1]+1] != painters)) {
paintedBy[i[1]] = painters;
if(!b) {
b = true;
sum+=i[0];
}
}
}
b = !b;
painters++;
for (int[] i : fences) {
if (paintedBy[i[1]] == 0) {
if ((i[1] == 0 || paintedBy[i[1]-1] != painters)
&&
(i[1] + 1 == fenceCount || paintedBy[i[1]+1] != painters)) {
paintedBy[i[1]] = painters;
actualPainters++;
if(!b) {
b = true;
sum+=i[0];
}
}
}
}
b = !b;
painters++;
for (int[] i : fences) {
if (paintedBy[i[1]] == 0) {
if ((i[1] == 0 || paintedBy[i[1]-1] != painters)&&(i[1] + 1 == fenceCount || paintedBy[i[1]+1] != painters)) {
paintedBy[i[1]] = painters;
actualPainters++;
if(!b) {
b = true;
sum+=i[0];
}
}
}
}
int l1, l2 = 0;
for (int i = 0; i < fenceCount; i++) {
if (i % 2 = 0) {
if (l1 < fences[i][0]) {
l1 = fences[i][0];
}
} else {
if (l2 < fences[i][0]) {
l2 = fences[i][0];
}
}
}
if (l1 + l2 < sum) {
int temp = l1 + l2;
System.out.print(temp + " ");
System.out.println("2");
for (int i = 0; i < fenceCount; i++) {
if (i % 2 = 0) {
System.out.println("1 ");
} else {
System.out.println("2 ");
}
}
} else {
System.out.print(sum + " ");
System.out.println(actualPainters);
for (int i : paintedBy) {
System.out.print(i + " ");
}
}
}
}
