В вашем университете обучается \(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]\)).
Суммарная разнообразность — это сумма разнообразностей по всем собранным команда.
Ваша задача — минимизировать суммарную разнообразность разделения студентов и найти оптимальный способ их разделить.
Выходные данные
В первой строке выведите два целых числа \(res\) и \(k\) — минимально возможную разнообразность разделения и количество команд в вашем разделении соответственно.
Во второй строке выведите \(n\) целых чисел \(t_1, t_2, \dots, t_n\) (\(1 \le t_i \le k\)), где \(t_i\) равно номеру команды, к которой принадлежит \(i\)-й студент.
Если существует несколько возможных ответов, выведите любой. Заметьте, что нет необходимости минимизировать количество команд. Каждая команда должна состоять хотя бы из трех студентов.
Примечание
В первом тестовом примере есть только одна команда с умениями \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 3 4 2
|
3 1
1 1 1 1 1
|
|
2
|
6
1 5 12 13 2 15
|
7 2
2 2 1 1 2 1
|
|
3
|
10
1 2 5 129 185 581 1041 1909 1580 8150
|
7486 3
3 3 3 2 2 2 2 1 1 1
|