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.
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class Main {
    private FastScanner in;
    private PrintWriter out;
    final int MOD = (int)1e9+7;
    long ceil(long a, long b){return (a + b - 1) / b;}
    long gcd(long a, long b){return b == 0 ? a : gcd(b, a % b);}
    long lcm(long a, long b){return a / gcd(a, b) * b; /*オーバーフローに注意*/}

    void solve() {
        int n = in.nextInt();
        int[][] a = new int[n+1][2];
        for(int i = 1; i <= n; i++){
            a[i][0] = in.nextInt();
            a[i][1] = i;
        }
        Arrays.sort(a, (e1, e2)->Integer.compare(e1[0], e2[0]));

        SegmentTree seg = new SegmentTree(n+1);
        long[] dp = new long[n+1];
        int[] pre = new int[n+1];
        Arrays.fill(dp, Long.MAX_VALUE / 2);
        dp[0] = 0;
        pre[0] = 0;
        seg.setPoint(0, dp[0] - a[1][0]);
        for(int i = 3; i <= n; i++){
            SegmentTree.Node res = seg.getSegment(0, i-2);
            dp[i] = res.value + a[i][0];
            pre[i] = res.index;
            if(i < n) seg.setPoint(i, dp[i] - a[i+1][0]);
            /*
            for(int j = 0; j <= i-3; j++){
                dp[i] = Math.min(dp[i], dp[j] + a[i] - a[j+1]);
            }
            */
        }

        int idx = n, cnt = 0;
        while(true){
            //out.println(dp[idx] + " " + pre[idx]);
            cnt++;
            for(int i = idx; i > pre[idx]; i--) a[i][0] = cnt;
            idx = pre[idx];
            if(idx == 0) break;
        }
        Arrays.sort(a, (e1, e2)->Integer.compare(e1[1], e2[1]));

        out.println(dp[n] + " " + cnt);
        for(int i = 1; i <= n; i++) out.print(a[i][0] + " ");
        out.println();
    }
    //end solve

    class SegmentTree{
        public class Node implements Comparable<Node>{
            long value;
            int index;
            public Node(long c, int i){
                value = c; index = i;
            }
            @Override
            public int compareTo(Node o) {
                return this.value != o.value ? Long.compare(this.value, o.value) : Integer.compare(this.index, o.index);
            }
        }

        int n;
        Node[] node;

        /*二項演算で使える単位元*/
        private long e = Integer.MAX_VALUE;
        //private long e = 0;

        /*結合律が成り立つ、要素同士の二項演算*/
        private Node f(Node e1, Node e2){
            //区間最小値、同じ値なら小さいindexを返す
            return e1.compareTo(e2) <= 0 ? e1 : e2;
        }

        /*要素更新用の演算(可換でなくてもよい)*/
        private long g(long nodeVal, long val){
            return val; //更新
        }

        /* 単位元で初期化 */
        public SegmentTree(int sz){
            n = 1;
            while(n < sz) n *= 2;
            node = new Node[2*n];
            for(int i = 0; i < node.length; i++) node[i] = new Node(e, 0);
            for(int i = 0; i < sz; i++) {
                node[i + n].value = e;
                node[i + n].index = i;
            }
            for(int i = n-1; i > 0; i--) {
                node[i] = f(node[2 * i + 0], node[2 * i + 1]);
            }
        }

        /* 元配列vでセグメント木を初期化 */
        public SegmentTree(long[] v){
            n = 1;
            while(n < v.length) n *= 2;
            node = new Node[2*n];
            for(int i = 0; i < v.length; i++) {
                node[i + n].value = v[i];
                node[i + n].index = i;
            }
            for(int i = n-1; i > 0; i--) {
                node[i] = f(node[2 * i + 0], node[2 * i + 1]);
            }
        }

        public Node getPoint(int x){
            return new Node(node[x + n].value, node[x + n].index);
        }

        /* 0-indexed:xの要素をg(node[x], val)に更新 */
        public void setPoint(int x, long val){
            x += n;
            node[x].value = g(node[x].value, val);
            while(x > 1){
                x = x / 2;
                node[x] = f(node[2*x+0], node[2*x+1]);
            }
        }

        /* 指定した区間[L,R)の区間演算の結果を求めるクエリ */
        public Node getSegment(int L, int R){
            L += n;
            R += n;
            Node resL = new Node(e, 0), resR = new Node(e, 0);
            while (L < R) {
                if ((L & 1) != 0){
                    resL = f(resL, node[L]);
                    L++;
                }
                if ((R & 1) != 0){
                    --R;
                    resR = f(resR, node[R]);
                }
                L >>= 1;
                R >>= 1;
            }
            Node res = f(resL, resR);
            return new Node(res.value, res.index);
        }
    }

    public static void main(String[] args) {
        new Main().m();
    }

    private void m() {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);
        /*
        try {
            String path = "output.txt";
            out = new PrintWriter(new BufferedWriter(new FileWriter(new File(path))));
        }catch (IOException e){
            e.printStackTrace();
        }
        */
        solve();
        out.flush();
        in.close();
        out.close();
    }

    static class FastScanner {
        private Reader input;

        public FastScanner() {this(System.in);}
        public FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}
        public void close() {
            try {
                this.input.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

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

        public long nextLong() {
            try {
                int sign = 1;
                int b = input.read();
                while ((b < '0' || '9' < b) && b != '-' && b != '+') {
                    b = input.read();
                }
                if (b == '-') {
                    sign = -1;
                    b = input.read();
                } else if (b == '+') {
                    b = input.read();
                }
                long ret = b - '0';
                while (true) {
                    b = input.read();
                    if (b < '0' || '9' < b) return ret * sign;
                    ret *= 10;
                    ret += b - '0';
                }
            } catch (IOException e) {
                e.printStackTrace();
                return -1;
            }
        }

        public double nextDouble() {
            try {
                double sign = 1;
                int b = input.read();
                while ((b < '0' || '9' < b) && b != '-' && b != '+') {
                    b = input.read();
                }
                if (b == '-') {
                    sign = -1;
                    b = input.read();
                } else if (b == '+') {
                    b = input.read();
                }
                double ret = b - '0';
                while (true) {
                    b = input.read();
                    if (b < '0' || '9' < b) break;
                    ret *= 10;
                    ret += b - '0';
                }
                if (b != '.') return sign * ret;
                double div = 1;
                b = input.read();
                while ('0' <= b && b <= '9') {
                    ret *= 10;
                    ret += b - '0';
                    div *= 10;
                    b = input.read();
                }
                return sign * ret / div;
            } catch (IOException e) {
                e.printStackTrace();
                return Double.NaN;
            }
        }

        public char nextChar() {
            try {
                int b = input.read();
                while (Character.isWhitespace(b)) {
                    b = input.read();
                }
                return (char) b;
            } catch (IOException e) {
                e.printStackTrace();
                return 0;
            }
        }

        public String nextStr() {
            try {
                StringBuilder sb = new StringBuilder();
                int b = input.read();
                while (Character.isWhitespace(b)) {
                    b = input.read();
                }
                while (b != -1 && !Character.isWhitespace(b)) {
                    sb.append((char) b);
                    b = input.read();
                }
                return sb.toString();
            } catch (IOException e) {
                e.printStackTrace();
                return "";
            }
        }

        public int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

        public int[] nextIntArrayDec(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt() - 1;
            }
            return res;
        }

        public int[] nextIntArray1Index(int n) {
            int[] res = new int[n + 1];
            for (int i = 0; i < n; i++) {
                res[i + 1] = nextInt();
            }
            return res;
        }

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

        public long[] nextLongArrayDec(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong() - 1;
            }
            return res;
        }

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

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