2-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"C" Портим порядок
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

На ковре в комнате у Димы в ряд нарисовано n точек. По удивительному совпадению у него также есть n кубиков, весом 1, 2, ..., n грамм, соответственно. Дима наигрался с кубиками и выложил их в ряд, по одному на точку. Теперь он собирался переложить их так, чтобы они шли слева направо по возрастанию веса, но немного отвлёкся. В этот момент в комнату вошёл вредный мальчик Вадим, и решил напакостить Диме.

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

Вадим — вредный мальчик, поэтому он хочет напакостить побольше. Он уже вытащил из ряда несколько кубиков и теперь хочет их расставить их обратно таким способом, чтобы Дима совершил максимальное число обменов. После возвращения кубиков те кубики, которые Вадим не вынимал, должны остаться на своих местах, около каждой точки должно оказаться ровно по одному кубику.

Как именно ему следует расположить кубики?

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t.

Каждый тест описывается следующим образом.

В первой строке описания теста содержится число n — общее количество кубиков (1 ≤ n ≤ 105). В следующей строке содержится n чисел ai (0 ≤ ai ≤ n)

Если ai равно 0, то на i-м месте пока ничего не стоит, этот кубик Вадим вынул. Иначе ai равно массе кубика, который стоит на i-м месте.

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

Сумма n по всем тестам одних входных данных не превосходит 105.

Формат выходных данных

Для каждого теста выведите две строки.

В первой строке выведите количество обменов, которые придётся совершить Диме для сортировки кубиков.

Во второй строке выведите n чисел — массы кубиков в порядке слева направо, которые получатся при оптимальной расстановке кубиков Вадимом. Обратите внимание, что кубики, которые Вадим не вынул сразу, должны остаться на своих местах.

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

Примеры
Входные данные
3
2
0 0
4
4 0 0 3
5
0 4 0 2 5
Выходные данные
1
2 1
3
4 1 2 3
2
3 4 1 2 5
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.