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


public class CP {
    public static void main(String[] args) throws Exception {
        /*new Thread(null, new Runnable() {
            @Override
            public void run() {
                try {
                    new Solver().solve();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }, "Solver", 1l << 30).start();*/

        new Solver().solve();
    }
}

class Solver {
    final Helper hp;
    final int MAXN = 1000_006;
    final long MOD = (long) 1e9 + 7;

    Solver() {
        hp = new Helper(MOD, MAXN);
        hp.initIO(System.in, System.out);
    }


    void solve() throws Exception {
        int i, j, k;

        int N = hp.nextInt();
        long[] A = hp.getLongArray(N);

        if (N <= 5) {
            System.out.println(hp.max(A) - hp.min(A));
            System.out.println(1);
            for (i = 0; i < N; ++i) System.out.print("1 ");
            System.out.println();
            return;
        }

        HashMap<Long, Stack<Integer>> map = new HashMap<>();
        for (i = 0; i < N; ++i) {
            map.putIfAbsent(A[i], new Stack<>());
            map.get(A[i]).add(i);
        }
        hp.shuffle(A);
        Arrays.sort(A);


        TreeSet<long[]> pairs = new TreeSet<>((long[] a, long[] b) ->
                a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));

        //System.out.println(Arrays.toString(A));

        dp = new long[N + 1];
        dp[0] = -A[0]; dp[1] = dp[2] = Long.MAX_VALUE;
        for (i = 3; i <= N; ++i) {
            pairs.add(new long[] {dp[i - 3], i - 3});
            dp[i] = pairs.first()[0] + A[i - 1];
            if (i < N) dp[i] -= A[i];
        }
        //System.out.println(Arrays.toString(dp));


        BitSet sel = new BitSet();
        int idx = N; sel.set(idx);
        while (idx > 0) {
            long temp = dp[idx] - A[idx - 1];
            if (idx < N) temp += A[idx];

            int prev = -7;
            while (prev < 0) {
                long[] p = pairs.floor(new long[] {temp, Integer.MAX_VALUE >> 2});
                pairs.remove(p);
                if (p[1] <= idx - 3) prev = (int) p[1];
            }
            if (dp[prev] != temp) System.exit(7 / 0);

            sel.set(prev);
            idx = prev;
        }


        int[] ans = new int[N];
        for (k = i = 0; i < N; ++i) {
            if (sel.get(i)) ++k;
            ans[i] = k;
        }

        long sum = 0;
        for (i = 1; i <= N; ++i) if (sel.get(i)) {
            sum += A[i - 1] - A[sel.previousSetBit(i - 1)];
        }

        int[] assignCol = new int[N];
        for (i = 0; i < N; ++i) {
            assignCol[map.get(A[i]).pop()] = ans[i];
        }

        hp.println(sum);
        hp.println(hp.max(assignCol));
        hp.println(hp.joinElements(assignCol));
        hp.flush();
    }

    long[] dp;

    long search(int l, int r) {
        long ret = Long.MAX_VALUE;
        for (int i = l; i <= r; ++i) ret = Math.min(ret, dp[i]);
        return ret;
    }
}

class Helper {
    final long MOD;
    final int MAXN;
    final Random rnd;

    public Helper(long mod, int maxn) {
        MOD = mod;
        MAXN = maxn;
        rnd = new Random();
    }


    public static int[] sieve;
    public static ArrayList<Integer> primes;

    public void setSieve() {
        primes = new ArrayList<>();
        sieve = new int[MAXN];
        int i, j;
        for (i = 2; i < MAXN; ++i)
            if (sieve[i] == 0) {
                primes.add(i);
                for (j = i; j < MAXN; j += i) {
                    sieve[j] = i;
                }
            }
    }


    public static long[] factorial;

    public void setFactorial() {
        factorial = new long[MAXN];
        factorial[0] = 1;
        for (int i = 1; i < MAXN; ++i) factorial[i] = factorial[i - 1] * i % MOD;
    }

    public long getFactorial(int n) {
        if (factorial == null) setFactorial();
        return factorial[n];
    }

    public long ncr(int n, int r) {
        if (r > n) return 0;
        if (factorial == null) setFactorial();
        long numerator = factorial[n];
        long denominator = factorial[r] * factorial[n - r] % MOD;
        return numerator * pow(denominator, MOD - 2, MOD) % MOD;
    }


    public long[] getLongArray(int size) throws Exception {
        long[] ar = new long[size];
        for (int i = 0; i < size; ++i) ar[i] = nextLong();
        return ar;
    }

    public int[] getIntArray(int size) throws Exception {
        int[] ar = new int[size];
        for (int i = 0; i < size; ++i) ar[i] = nextInt();
        return ar;
    }

    public String[] getStringArray(int size) throws Exception {
        String[] ar = new String[size];
        for (int i = 0; i < size; ++i) ar[i] = next();
        return ar;
    }

    public String joinElements(long[] ar) {
        StringBuilder sb = new StringBuilder();
        for (long itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }


    public String joinElements(int[] ar) {
        StringBuilder sb = new StringBuilder();
        for (int itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }

    public String joinElements(String[] ar) {
        StringBuilder sb = new StringBuilder();
        for (String itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }

    public String joinElements(Object[] ar) {
        StringBuilder sb = new StringBuilder();
        for (Object itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }


    public long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }


    public long max(long[] ar) {
        long ret = ar[0];
        for (long itr : ar) ret = Math.max(ret, itr);
        return ret;
    }

    public int max(int[] ar) {
        int ret = ar[0];
        for (int itr : ar) ret = Math.max(ret, itr);
        return ret;
    }

    public long min(long[] ar) {
        long ret = ar[0];
        for (long itr : ar) ret = Math.min(ret, itr);
        return ret;
    }

    public int min(int[] ar) {
        int ret = ar[0];
        for (int itr : ar) ret = Math.min(ret, itr);
        return ret;
    }


    public long sum(long[] ar) {
        long sum = 0;
        for (long itr : ar) sum += itr;
        return sum;
    }

    public long sum(int[] ar) {
        long sum = 0;
        for (int itr : ar) sum += itr;
        return sum;
    }

    public void shuffle(int[] ar) {
        int r;
        for (int i = 0; i < ar.length; ++i) {
            r = rnd.nextInt(ar.length);
            if (r != i) {
                ar[i] ^= ar[r];
                ar[r] ^= ar[i];
                ar[i] ^= ar[r];
            }
        }
    }

    public void shuffle(long[] ar) {
        int r;
        for (int i = 0; i < ar.length; ++i) {
            r = rnd.nextInt(ar.length);
            if (r != i) {
                ar[i] ^= ar[r];
                ar[r] ^= ar[i];
                ar[i] ^= ar[r];
            }
        }
    }

    public long pow(long base, long exp, long MOD) {
        base %= MOD;
        long ret = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) ret = ret * base % MOD;
            base = base * base % MOD;
            exp >>= 1;
        }
        return ret;
    }


    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static BufferedWriter bw;


    public void initIO(InputStream is, OutputStream os) {
        try {
            in = is;
            bw = new BufferedWriter(new OutputStreamWriter(os));
        } catch (Exception e) {
        }
    }

    public void initIO(String inputFile, String outputFile) {
        try {
            in = new FileInputStream(inputFile);
            bw = new BufferedWriter(new OutputStreamWriter(
                    new FileOutputStream(outputFile)));
        } catch (Exception e) {
        }
    }

    private int scan() throws Exception {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0)
                return -1;
        }
        return buf[index++];
    }

    public String next() throws Exception {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan())
            sb.append((char) c);
        return sb.toString();
    }

    public int nextInt() throws Exception {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    public long nextLong() throws Exception {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    public void print(Object a) throws Exception {
        bw.write(a.toString());
    }

    public void printsp(Object a) throws Exception {
        print(a);
        print(" ");
    }

    public void println() throws Exception {
        bw.write("\n");
    }

    public void println(Object a) throws Exception {
        print(a);
        println();
    }

    public void flush() throws Exception {
        bw.flush();
    }
}
