E. Очередное разделение на команды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В вашем университете обучается $$$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]$$$).

Суммарная разнообразность — это сумма разнообразностей по всем собранным команда.

Ваша задача — минимизировать суммарную разнообразность разделения студентов и найти оптимальный способ их разделить.

Входные данные

Первая строка входных данных содержит одно целое число $$$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$$$-го студента.

Выходные данные

В первой строке выведите два целых числа $$$res$$$ и $$$k$$$ — минимально возможную разнообразность разделения и количество команд в вашем разделении соответственно.

Во второй строке выведите $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_i \le k$$$), где $$$t_i$$$ равно номеру команды, к которой принадлежит $$$i$$$-й студент.

Если существует несколько возможных ответов, выведите любой. Заметьте, что нет необходимости минимизировать количество команд. Каждая команда должна состоять хотя бы из трех студентов.

Примеры
Входные данные
5
1 1 3 4 2
Выходные данные
3 1
1 1 1 1 1
Входные данные
6
1 5 12 13 2 15
Выходные данные
7 2
2 2 1 1 2 1
Входные данные
10
1 2 5 129 185 581 1041 1909 1580 8150
Выходные данные
7486 3
3 3 3 2 2 2 2 1 1 1
Примечание

В первом тестовом примере есть только одна команда с умениями $$$[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$$$.