Codeforces Round 217 (Div. 2) |
---|
Закончено |
В школе Васе на лето задали прочитать внушительный список книг. Вася, в отличие от многих современных школьников, любит читать, поэтому он каждый день лета читал какую-нибудь книгу.
Читая книги, Вася вел дневник летнего чтения, в котором он для каждого дня отмечал порядковый номер книги из списка, которую он читал в этот день. Книги в списке нумеруются с 1, и Вася читает их именно в том порядке, в котором они идут в списке. Вася никогда не переходит к следующей книге из списка, пока не дочитал текущую до конца. К сожалению, Вася вел дневник не очень ответственно, поэтому в некоторые дни он забывал отметить номер книги, и записи для этих дней остались пустыми.
Поскольку Вася знает, что учительница литературы обязательно потребует сдать ей дневник чтения, ему нужно восстановить отсутствующие записи в дневнике. Помогите ему это сделать и заполните все пропуски. Вася точно знает, что на каждую книгу он тратил не менее двух дней, но и не более пяти дней. Все книги, которые Вася начинал читать, он дочитал за лето до конца. При восстановлении пропусков можно считать, что в списке на лето было очень много книг (настолько много, что их все невозможно прочитать за лето). Если существует несколько способов корректным образом восстановить записи в дневнике, то Вася предпочтет такой способ, из которого бы следовало, что он прочитал за лето наибольшее количество книг.
В первой строке записано целое число n — количество дней лета (2 ≤ n ≤ 2·105). Во второй строке записано n целых чисел a1, a2, ... an — записи в дневнике в порядке их внесения (0 ≤ ai ≤ 105). В случае, если в i-й день Вася забыл записать номер книги, ai равно 0.
Если невозможно корректно заполнить пропуски в дневнике (возможно, он изначально содержал ошибки), выведите «-1».
Иначе в первой строке выведите максимальное количество книг, которое Вася мог, согласно дневнику, прочитать за лето. Во второй строке выведите n чисел — дневник с корректно вставленными записями. Если оптимальных решений несколько, разрешается вывести любое из них.
7
0 1 0 0 0 3 0
3
1 1 2 2 3 3 3
8
0 0 0 0 0 0 0 0
4
1 1 2 2 3 3 4 4
4
0 0 1 0
1
1 1 1 1
4
0 0 0 3
-1
Название |
---|