CF1256E.Yet Another Division Into Teams

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 \cdot 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], \dots, a[i_k]$, then the diversity of this team is $\max\limits_{j=1}^{k} a[i_j] - \min\limits_{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.

你们学校共有 $n$ 名学生。第 $i$ 名学生的编程能力为 $a_i$。作为教练，你希望将他们分组，以备战即将到来的 ICPC 总决赛。试想一下，若一所大学竟有 $2 \cdot 10^5$ 名学生已做好总决赛准备，该是多么优秀！

每支队伍至少需包含三名学生；每名学生必须且仅能属于一支队伍。一支队伍的多样性定义为该队中某位学生最高编程能力与某位学生最低编程能力之差（换言之，若该队由 $k$ 名学生组成，其编程能力分别为 $a[i_1], a[i_2], \dots, a[i_k]$，则该队的多样性为 $\max\limits_{j=1}^{k} a[i_j] - \min\limits_{j=1}^{k} a[i_j]$）。

总多样性即所有组建队伍的多样性之和。

你的任务是：最小化学生分组方案的总多样性，并找出最优分组方式。

The first line of the input contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of students.

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

输入的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）—— 学生人数。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示第 $i$ 个学生的编程技能值。

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, \dots, t_n$ ($1 \le t_i \le 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.

第一行输出两个整数 $res$ 和 $k$ —— 分组后学生的最小总多样性值，以及你所划分的队伍数量。

第二行输出 $n$ 个整数 $t_1, t_2, \dots, t_n$（$1 \le t_i \le k$），其中 $t_i$ 表示第 $i$ 个学生所属的队伍编号。

若存在多个合法答案，输出任意一个即可。注意：你无需最小化队伍数量。每支队伍至少应包含三名学生。

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$.

在第一个例子中，只有一支队伍，其技能值为 $[1, 1, 2, 3, 4]$，因此答案为 $3$。可以证明无法得到更优的答案。

在第二个例子中，有两支队伍，其技能值分别为 $[1, 2, 5]$ 和 $[12, 13, 15]$，因此答案为 $4 + 3 = 7$。

在第三个例子中，有三支队伍，其技能值分别为 $[1, 2, 5]$、$[129, 185, 581, 1041]$ 和 $[1580, 1909, 8150]$，因此答案为 $4 + 912 + 6570 = 7486$。