#674. [CZOI2023 B] 奶牛农场

[CZOI2023 B] 奶牛农场

题目描述

小 X 是 CZ 市著名的农场主,他拥有着 CZ 市最大的奶牛农场。农场里有一排牛棚,一共 nn 个牛棚,从左到右依次编号为 1,2,.,n1,2,….,n 。目前有些牛棚里住着奶牛,有些牛棚还是空的。

每个奶牛有一个高度,其中第 ii 个牛棚里的奶牛的高度为 HiH_i ,如果第 ii 个牛棚里没有奶牛的话, Hi=0H_i=0 ,为了使小 X 的牛棚变得美观,他打算去市场上买一些奶牛放到空着的牛棚里(假设市场上能买到任意多个高度在 1110910^9 之间的任意正整数的奶牛),使得每个牛棚里都有一头奶牛,并且高度从左往右严格递增。

请你告诉小X 是否能让他的牛棚变得美观,如果可以请给出一个任意合法的方案。

输入格式

第一行 11 个正整数 nn ,表示牛棚个数。

第二行 nn 个非负整数 HiH_i ,如果 Hi=0H_i=0 说明第 ii 个牛棚是空的,否则说明第 ii 个牛棚里面有一个高度为 HiH_i 的奶牛。

输出格式

第一行输出一个字符串 YESNO。如果让他的牛棚变得美观,则输出 YES,否则输出 NO

如果第一行输出 YES,再输出第二行 nn 个正整数 1Hi1091\leq H'_i\leq 10^9 ,你需要保证对所有 1in11\leq i\leq n-1 满足 Hi<Hi+1H'_i<H'_{i+1} ,并且如果 Hi>0H'_i>0 ,那么 Hi=HiH'_i=H_i ,如果有多种合法的 方案,输出任意一种即可。

3
0 0 0
YES
4 5 6
4
0 2 0 4
YES
1 2 3 4
4
0 0 0 2
NO
2
1000000000 0
NO

提示

样例 33 解释

因为高度是正整数,还要严格递增,所以第 44 头奶牛的高度必须 2\geq 2 。所以不存在满足题目条件的方案。

样例 44 解释

因为买不到高度为 >109>10^9 的奶牛,所以不存在满足题目条件的方案。

数据范围

测试点 nn HiH_i
对于测试点 151-5 1n51\leq n\leq 5 0Hi100\leq H_i\leq10
对于测试点 696-9 1n1051\leq n\leq 10^5 0Hi1090\leq H_i\leq 10^9