C. Лабораторная работа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аня и Кирилл делают лабораторную работу по физике. В одном из заданий необходимо n раз измерить некоторую величину, чтобы уменьшить ошибку, и вычислить среднее значение.

Кирилл выполнил необходимые измерения, получив целочисленные значения x1, x2, ..., xn. Важно отметить, что разброс измеренных значений не очень большой, а именно, максимальное измеренное значение не более чем на 2 превосходит минимально измеренное значение.

Ане лень делать измерения, но просто так списать все измерения у Кирилла она не может, ведь величина ошибки — случайная величина, и если все измерения совпадут, преподаватель заподозрит неладное. Аня хочет написать в своей работе такие целочисленные величины измерений y1, y2, ..., yn, что выполняются следующие условия:

  • среднее значение среди величин x1, x2, ..., xn точно равно среднему значению y1, y2, ..., yn;
  • все измерения в работе Ани лежат в тех же пределах, что и измерения Кирилла, то есть максимальное значение среди измерений Ани не превосходит максимальное значение среди измерений Кирилла, а минимальное значение среди измерений в работе Ани не меньше, чем минимальное значение среди измерений Кирилла;
  • количество совпадающих измерений у Ани и Кирилла — минимально возможное при выполнении предыдущих условий. Формально, учитель смотрит на все измерения Ани по очереди, если такое же измерение есть у Кирилла и оно еще не зачеркнуто, он вычеркивает одно это измерение у Ани и одно из таких измерений у Кирилла. Количеством совпадающих измерений называется количество зачеркнутых измерений у Ани.

Помогите Ане написать такой набор измерений, чтобы выполнялись условия, перечисленные выше.

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

В первой строке следует целое число n (1 ≤ n ≤ 100 000) — количество измерений, которые сделал Кирилл.

Во второй строке следует последовательность x1, x2, ..., xn ( - 100 000 ≤ xi ≤ 100 000) — результаты измерений Кирилла. Гарантируется, что разность между максимальным и минимальным значением среди чисел x1, x2, ..., xn не превосходит 2.

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

В первую строку выведите минимальное количество совпадающих измерений.

Во вторую строку выведите n целых чисел y1, y2, ..., yn — результаты измерений Ани. Числа могут быть выведены в любом порядке. Помните, что минимальное из измерений Ани должно быть не меньше, чем минимум из измерений Кирилла, а максимальное из измерений Ани должно быть не больше, чем максимум из измерений Кирилла.

Если существует несколько решений, выведите любое.

Примеры
Входные данные
6
-1 1 1 0 0 -1
Выходные данные
2
0 0 0 0 0 0
Входные данные
3
100 100 101
Выходные данные
3
101 100 100
Входные данные
7
-10 -9 -10 -8 -10 -9 -9
Выходные данные
5
-10 -10 -9 -9 -9 -9 -9
Примечание

В первом примере Аня может записать нули в качестве каждого из результатов измерений. Тогда средняя величина её измерений будет равна средней величине измерений Кирилла, а совпадающих измерений будет всего два.

Во втором примере Аня должна записать два результата измерений, равные 100, и одно 101 (сами измерения она может записать в любом порядке), потому что только в этом случае средняя величина её измерений будет равна средней величине измерений Кирилла. Таким образом, все три измерения будут совпадать.

В третьем примере количество совпадающих измерений равно 5.