← 返回题目列表

Codeforces · 370/E

E. 暑期阅读

中文机器翻译题面 查看原题

在学校,瓦西亚得到了一份令人印象深刻的暑期阅读书籍清单。与其他现代小学生不同,瓦夏喜欢读书,所以他夏天每天都会读一些书。

Vasya 一边读书,一边在读者日记中做笔记。每天他都会写下他正在读的书的序号。列表中的书籍从 1 开始编号,Vasya 正在按照列表中的顺序阅读它们。瓦夏在读完上一本之前不会读新书。不幸的是,瓦夏并不准确,有时他忘记记下这本书的编号,而那些日子的笔记仍然是空的。

由于Vasya知道文学老师会想要查看读者日记,所以他需要恢复丢失的记录。帮助他完成并填补所有空白。瓦夏确信他每本书至少要花两天、最多五天的时间。瓦夏读完了他开始读的所有书。假设阅读清单包含很多书。事实上,太多了,不可能在一个夏天读完所有这些书。如果有多种有效的方法来恢复日记记录,Vasya 更喜欢显示最大阅读书籍数的方法。

输入

第一行包含整数 n — 夏季天数 (2 ≤ n ≤ 2·105)。第二行包含 n 个整数 a1, a2, ... an — 日记中的记录按写入顺序排列 (0 ≤ ai ≤ 105)。如果 Vasya 在第 i 天忘记写下这本书的编号,则 ai 等于 0。

输出

如果无法正确填写日记中的空白(日记最初可能包含错误),则打印“-1”。

否则,在第一行打印如果我们坚持写日记的话,Vasya 在夏天可以读的最大书本数。在第二行中打印 n 个整数——正确插入记录的日记。如果有多个最优解,可以打印任意一个。

示例

输入 #1

7
0 1 0 0 0 3 0

输出 #1

3
1 1 2 2 3 3 3

输入 #2

8
0 0 0 0 0 0 0 0

输出 #2

4
1 1 2 2 3 3 4 4

输入 #3

4
0 0 1 0

输出 #3

1
1 1 1 1

输入#4

4
0 0 0 3

输出#4

-1