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.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.util.Comparator.*;

public class Main {
    FastScanner in;
    PrintWriter out;
    ArrayList<Integer>[] graph;
    ArrayList<GraphPair>[] weightedGraph;
    long mod = (long) 1e9 + 7; // 998_244_353L || (long) 1e9 + 9
    boolean multitests = false;

    private void solve() throws IOException {
        // solveA();
        // solveB();
        // solveC();
        // solveD();
        solveE();
        // solveF();
    }

    private void solveA() throws IOException {
        long a = in.nextLong(), b = in.nextLong(), n = in.nextLong(), S = in.nextLong();
        out.println(S % n <= b && n * a + b >= S ? "YES" : "NO");
    }

    private void solveB() throws IOException {
        int n = in.nextInt();
        int[] p = in.nextIntArray(n);

        boolean[] used = new boolean[n + 1];
        for (int l = 0, r = 0, next = 1; l < n; l = r) {
            while (p[r] != next)
                r++;

            if (l == r) {
                used[next++] = true;
                r++;
            } else {
                for (int i = r; i > l; i--)
                    p[i] = p[i - 1];
                p[l] = next++;
                for (int i = l; i < r; i++)
                    used[p[i]] = true;
            }
            while (next <= n && used[next])
                next++;
        }

        for (int i = 0; i < n; i++)
            out.print(p[i] + " ");
        out.println();
    }

    private void solveC() throws IOException {
        int n = in.nextInt(), m = in.nextInt(), d = in.nextInt();
        int[] c = in.nextIntArray(m);
        int sum = (int) sumInt(c);
        if ((d - 1) * (m + 1) + sum >= n) {
            out.println("YES");
            int zero = n - sum;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < d - 1 && zero-- > 0; j++)
                    out.print("0 ");
                for (int j = 0; j < c[i]; j++)
                    out.print(i + 1 + " ");
            }
            while (zero-- > 0)
                out.print("0 ");
        } else {
            out.println("NO");
        }
    }

    private void solveD() throws IOException {
        int n = in.nextInt();
        long k = in.nextLong();
        char[] s = in.next().toCharArray();

        long cnt = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                sum += cnt;

                if (sum > k) {
                    sum -= cnt;

                    char[] ans = new char[n];
                    for (int j = 0; j < i - cnt; j++)
                        ans[j] = '0';
                    for (int j = 0; j < cnt; j++)
                        ans[i - (int) cnt + j] = '1';
                    ans[i] = '0';
                    for (int j = i + 1; j < n; j++)
                        ans[j] = s[j];

                    for (int j = i; sum++ < k; j--) {
                        ans[j] = '1';
                        ans[j - 1] = '0';
                    }

                    out.println(new String(ans));
                    return;
                }

            } else
                cnt++;
        }

        for (int i = 0; i < n - cnt; i++)
            out.print("0");
        for (int i = 0; i < cnt; i++)
            out.print("1");
        out.println();
    }

    class Pair {
        int a, id;

        Pair(int a, int id) {
            this.a = a;
            this.id = id;
        }
    }

    private void solveE() throws IOException {
        int n = in.nextInt();
        Pair[] a = new Pair[n];
        for (int i = 0; i < n; i++)
            a[i] = new Pair(in.nextInt(), i);

        sort(a, comparingInt(o -> o.a));

        long[] dp = new long[n], p = new long[n];
        fill(dp, Long.MAX_VALUE / 3);
        fill(p, -1);

        for (int i = 2; i < n; i++) {
            for (int len = 3; len < 6 && i - len >= -1; len++) {
                if (dp[i] > (i - len == -1 ? 0 : dp[i - len]) + a[i].a - a[i - len + 1].a) {
                    p[i] = len;
                    dp[i] = (i - len == -1 ? 0 : dp[i - len]) + a[i].a - a[i - len + 1].a;
                }
            }
        }

        int cnt = 0;
        for (int i = n - 1; i >= 0; i -= p[i], cnt++) {
            for (int j = 0; j < p[i]; j++) {
                a[i - j].a = cnt;
            }
        }

        out.println(dp[n - 1] + " " + cnt);
        sort(a, comparingInt(o -> o.id));
        for (int i = 0; i < n; i++)
            out.print(a[i].a + 1 + " ");
    }

    private void solveF() throws IOException {

    }

    void shuffleInt(int[] a) {
        Random random = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int swap = a[j];
            a[j] = a[i];
            a[i] = swap;
        }
    }

    void shuffleLong(long[] a) {
        Random random = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            long swap = a[j];
            a[j] = a[i];
            a[i] = swap;
        }
    }

    void reverseInt(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    void reverseLong(long[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            long swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    int maxInt(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++)
            if (max < a[i])
                max = a[i];
        return max;
    }

    long maxLong(long[] a) {
        long max = a[0];
        for (int i = 1; i < a.length; i++)
            if (max < a[i])
                max = a[i];
        return max;
    }

    int minInt(int[] a) {
        int min = a[0];
        for (int i = 1; i < a.length; i++)
            if (min > a[i])
                min = a[i];
        return min;
    }

    long minLong(long[] a) {
        long min = a[0];
        for (int i = 1; i < a.length; i++)
            if (min > a[i])
                min = a[i];
        return min;
    }

    long sumInt(int[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++)
            s += a[i];
        return s;
    }

    long sumLong(long[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++)
            s += a[i];
        return s;
    }

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

    long binpowmod(long a, long n) {
        long res = 1;
        a %= mod;
        n %= mod - 1;
        while (n > 0) {
            if (n % 2 == 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
            n /= 2;
        }
        return res;
    }

    class GraphPair implements Comparable<GraphPair> {
        int v;
        long w;

        GraphPair(int v, long w) {
            this.v = v;
            this.w = w;
        }

        public int compareTo(GraphPair o) {
            return w != o.w ? Long.compare(w, o.w) : Integer.compare(v, o.v);
        }
    }

    ArrayList<Integer>[] createGraph(int n) throws IOException {
        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    ArrayList<GraphPair>[] createWeightedGraph(int n) throws IOException {
        ArrayList<GraphPair>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s), 32768);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextInt();
            return a;
        }

        int[][] nextIntTable(int n, int m) throws IOException {
            int[][] a = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = in.nextInt();
            return a;
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextLong();
            return a;
        }

        long[][] nextLongTable(int n, int m) throws IOException {
            long[][] a = new long[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = in.nextLong();
            return a;
        }

        ArrayList<Integer>[] nextGraph(int n, int m, boolean directed) throws IOException {
            ArrayList<Integer>[] graph = createGraph(n);
            for (int i = 0; i < m; i++) {
                int v = in.nextInt() - 1, u = in.nextInt() - 1;
                graph[v].add(u);
                if (!directed)
                    graph[u].add(v);
            }
            return graph;
        }

        ArrayList<GraphPair>[] nextWeightedGraph(int n, int m, boolean directed) throws IOException {
            ArrayList<GraphPair>[] graph = createWeightedGraph(n);
            for (int i = 0; i < m; i++) {
                int v = in.nextInt() - 1, u = in.nextInt() - 1;
                long w = in.nextLong();
                graph[v].add(new GraphPair(u, w));
                if (!directed)
                    graph[u].add(new GraphPair(v, w));
            }
            return graph;
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }

    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        for (int t = multitests ? in.nextInt() : 1; t-- > 0; )
            solve();

        out.flush();
        out.close();
    }

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