There are n students at your university. The programming skill of the i-th student is a_i. As a coach, you want to divide them into teams to prepare them for the upcoming ICPC finals. Just imagine how good this university is if it has 2 ⋅ 10^5 students ready for the finals!

Each team should consist of at least three students. Each student should belong to exactly one team. The diversity of a team is the difference between the maximum programming skill of some student that belongs to this team and the minimum programming skill of some student that belongs to this team (in other words, if the team consists of k students with programming skills a[i_1], a[i_2], ..., a[i_k], then the diversity of this team is max_{j=1}^{k} a[i_j] - min_{j=1}^{k} a[i_j]).

The total diversity is the sum of diversities of all teams formed.

Your task is to minimize the total diversity of the division of students and find the optimal way to divide the students.

Input

The first line of the input contains one integer n (3 ≤ n ≤ 2 ⋅ 10^5) — the number of students.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the programming skill of the i-th student.

Output

In the first line print two integers res and k — the minimum total diversity of the division of students and the number of teams in your division, correspondingly.

In the second line print n integers t_1, t_2, ..., t_n (1 ≤ t_i ≤ k), where t_i is the number of team to which the i-th student belong.

If there are multiple answers, you can print any. Note that you don't need to minimize the number of teams. Each team should consist of at least three students.

Examples

Input


5
1 1 3 4 2


Output


3 1
1 1 1 1 1 


Input


6
1 5 12 13 2 15


Output


7 2
2 2 1 1 2 1 


Input


10
1 2 5 129 185 581 1041 1909 1580 8150


Output


7486 3
3 3 3 2 2 2 2 1 1 1 

Note

In the first example, there is only one team with skills [1, 1, 2, 3, 4] so the answer is 3. It can be shown that you cannot achieve a better answer.

In the second example, there are two teams with skills [1, 2, 5] and [12, 13, 15] so the answer is 4 + 3 = 7.

In the third example, there are three teams with skills [1, 2, 5], [129, 185, 581, 1041] and [1580, 1909, 8150] so the answer is 4 + 912 + 6570 = 7486.
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class YetAnotherDivisionIntoTeam implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new YetAnotherDivisionIntoTeam(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        Pair[] a = new Pair[N + 1];
        a[0] = new Pair(0, 0);
        for (int i = 1; i <= N; i++) {
            a[i] = new Pair(i, sc.nextInt());
        }
        Arrays.sort(a, Comparator.comparingLong(p -> p.val));
        SegmentTree dp = new SegmentTree(N + 1);
        dp.update(0, -a[1].val);
        dp.update(1, oo);
        dp.update(2, oo);
        int[] prev = new int[N + 1];
        for (int i = 3; i <= N; i++) {
            Pair prevPair = dp.query(0, i - 3);
//            System.out.println("Prev: " + prevPair);
            prev[i] = prevPair.idx;
            dp.update(i, a[i].val + prevPair.val - (i != N ? a[i + 1].val : 0));
//            dp.print();
        }
        int[] team = new int[N + 1];
        int t = 1;
        int curr = N;
        while (curr > 0) {
            int next = prev[curr];
            for (int j = curr; j > next; j--) {
                team[a[j].idx] = t;
            }
            t++;
            curr = next;
        }
        out.println(dp.query(N, N).val + " " + (t - 1));
        StringJoiner sj = new StringJoiner(" ");
        for (int i = 1; i <= N; i++) {
            sj.add(Integer.toString(team[i]));
        }
        out.println(sj.toString());
        out.close();
    }
    static long oo = (long) 9e18;

    static class Pair {
        int idx; long val;
        public Pair(int ii, long vv) {
            idx = ii; val = vv;
        }
        public String toString() {
            return "(" + idx + ", " + val + ")";
        }
    }

    static class SegmentTree {
        Pair[] tree;
        int N;
        public SegmentTree(int size) {
            N = size;
            tree = new Pair[4 * N + 1];
            Arrays.setAll(tree, i -> new Pair(-1, oo));
        }

        public void print() {
            StringJoiner sj = new StringJoiner(" ");
            for (int i = 0; i <= N; i++) {
                sj.add(query(i, i).toString());
            }
            System.out.println(sj);
        }

        public Pair query(int l, int r) {
            return query(1, 0, N - 1, l, r);
        }
        public Pair query(int node, int sl, int sr, int l, int r) {
            if (sr < l || r < sl) {
                return new Pair(-1, oo);
            } else if (l <= sl && sr <= r) {
                return tree[node];
            } else {
                int mid = (sl + sr) / 2;
                Pair left = query(2 * node, sl, mid, l, r);
                Pair right = query(2 * node + 1, mid + 1, sr, l, r);
                return left.val < right.val ? left : right;
            }
        }

        public void update(int i, long val) {
            update(1, 0, N - 1, i, val);
        }

        public void update(int node, int sl, int sr, int i, long val) {
            if (sr < i || i < sl) return;
            else if (i == sl && sr == i) {
                tree[node] = new Pair(sl, val);
            } else {
                int mid = (sl + sr) / 2;
                update(2 * node, sl, mid, i, val);
                update(2 * node + 1, mid + 1, sr, i, val);
                if (tree[2 * node].val < tree[2 * node + 1].val) {
                    tree[node] = tree[2 * node];
                } else {
                    tree[node] = tree[2 * node + 1];
                }
            }
        }
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }

    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}