У Ивана есть массив, состоящий из n элементов. Каждый из элементов — целое число от 1 до n.
Совсем недавно Иван узнал о перестановках и их лексикографическом порядке. Теперь он хочет изменить значения минимального количества элементов в своём массиве таким образом, чтобы его массив стал перестановкой (то есть каждое из целых чисел от 1 до n встречалось в его массиве ровно по одному разу). Если существует много способов сделать заданный массив перестановкой за минимальное количество изменений, то среди них Иван хочет выбрать такой, что полученная перестановка лексикографически минимальна.
Таким образом, в первую очередь Иван хочет минимизировать количество измененных элементов, а во вторую — минимизировать лексикографически полученную перестановку.
Для того, чтобы определить, какая из двух перестановок лексикографически меньше, они сначала сравниваются по первому элементу. При их равенстве — по второму, и так далее. Среди двух перестановок x и y лексикографически меньше будет x, если xi < yi, где i — первый индекс, в котором перестановки x и y различаются.
Определите, как будет выглядеть массив Ивана, если он осуществит задуманное.
Выходные данные
В первую строку выведите q — минимальное количество элементов, которые нужно изменить в массиве Ивана для того, чтобы массив стал перестановкой. Во вторую строку выведите лексикографически минимальную перестановку, которая получается с помощью q изменений.
Примечание
В первом примере нужно заменить тройку, стоящую в позиции 1, на единицу, а двойку, стоящую в позиции 3, нужно заменить на четвёрку. Тогда мы получим перестановку [1, 2, 4, 3], изменив два числа — эта перестановка лексикографически минимальная из всех подходящих перестановок.
Во втором примере ничего изменять не нужно, так как данный массив является перестановкой.