Yet Another Division Into Teams
Contest: Codeforces Round 598 (Div. 3)
Difficulty rating: 2000
Tags: dp, greedy, sortings

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
5
1 1 3 4 2

Example output:
3 1
1 1 1 1 1

Example input:
6
1 5 12 13 2 15

Example output:
7 2
2 2 1 1 2 1

Editorial:
Let's sort all students by their programming skills but save the initial indices to restore the answer.
Now we can understand that we don't need to compose the team of size greater than $$$5$$$ because in this case we can split it into more teams with fewer participants and obtain the same or even less answer.
Now we can do the standard dynamic programming $$$dp_{i}$$$ — the minimum total diversity of the division if we divided the first $$$i$$$ students (in sorted order). Initially, $$$dp_{0} = 0$$$, all other values of $$$dp$$$ are $$$+\infty$$$. Because of the fact above, we can do only three transitions ($$$0$$$-indexed):
• $$$dp_{i + 3} = min(dp_{i + 3}, dp_{i} + a_{i + 2} - a_{i})$$$;
• $$$dp_{i + 4} = min(dp_{i + 4}, dp_{i} + a_{i + 3} - a_{i})$$$;
• $$$dp_{i + 5} = min(dp_{i + 5}, dp_{i} + a_{i + 4} - a_{i})$$$.
The answer is $$$dp_{n}$$$ and we can restore it by standard carrying parent values (as a parent of the state we can use, for example, the number of participants in the team).