|
Имеется N камней разного веса.
Требуется разложить их на две кучки так, чтобы разница весов этих кучек была как можно меньше.
Input
В первой строке входного файла находится число N - количество камней (1<=N<=100).
В следующих строках располагаются N целых чисел - веса камней (в интервале от 1 до 1000).
Числа разделяются пробелами и/или переводами строк.
Output
Выведите в первой строчке одно число - минимально возможный модуль разности весов кучек.
В следующей строчке выведите через пробел N чисел 1 или 2, где 1 означает, что соответствующий камень пойдёт в 1-ю кучу, 2 - во вторую.
Если правильных решений несколько, выведите любое.
Sample
| Input | Output |
|---|
4
1 5 2 3
| 1
1 1 2 2
|
| 