题面

Description

从前有 $n$n 块石头排成一排，编号从$1$1到$n$n。有 $n$n 只青蛙站在这 $n$n 块石头上，其中编号为 $i$i 的青蛙站在编号 $i$i 的石头上。

这 $n$n 只青蛙有一个秘密计划，在某个风和日丽的早上，它们同时起跳，编号为 $i$i 的青蛙跳到编号为 $p_i$pi​ 的石头上。跳跃之后，每个石头上仍然有且仅有一只青蛙。即： $p_i$pi​ 为一个 $1$1 到 $n$n 的全排列。

天上有颗卫星，可以监控青蛙的跳动。由于一些技术原因，卫星只能提供有限的信息：对于 $(i,i+1)$(i,i+1) 区间（其中 $1≤i&lt;n$1≤i<n），有多少只青蛙经过此区间。例如：一只青蛙从编号为$4$4的石头跳到编号为$1$1的石头，它将依次经过 $(3,4)$(3,4), $(2,3)$(2,3), $(1,2)$(1,2) 共三个区间。

我们想根据卫星提供的信息还原出每只青蛙跳到哪块石头上（即 $p_i$pi​ ）。

Input

第一行一个整数 $n$n ，表示青蛙数量 $(2≤n≤2×10^5)$(2≤n≤2×105)

第二行包含 $n−1$n−1 个整数 $a_1,a_2,⋯a_{n−1}(0≤a_i≤2×10^5)$a1​,a2​,⋯an−1​(0≤ai​≤2×105) ，其中 $a_i$ai​ 表示有多少只青蛙经过 $(i,i+1)$(i,i+1) 区间。

Output

如果不存在跳跃方案，输出No

否则在第一行输出Yes，第二行输出 $n$n 个整数 $p_1,p_2,⋯,p_n$p1​,p2​,⋯,pn​ 。如果有多组解，输出任意一种。

Sample Input & Sample Output

【样例输入1】

5
2 4 2 2

【样例输出1】

Yes
4 3 2 5 1

【样例输入2】

4
1 2 3

【样例输出2】

No

HINT

【数据范围与约定】

子任务1（$10$10分）： $1≤n≤10$1≤n≤10

子任务2（$40$40分）： $1≤n≤2000$1≤n≤2000

子任务3（$50$50分）： $1≤n≤2×10^5$1≤n≤2×105

题解

首先注意到一个性质：每一个$a[i]$a[i]都得是偶数（如果左边跳一只青蛙到右边，则右边必定有一只青蛙跳到左边，这样会使$a[i]$a[i]加两次）。

然后，我们考虑相邻的两个$a$a：$a[i-1]$a[i−1]与$a[i]$a[i]。

它们只能有这三种关系：

1. $a[i-1]=a[i]$a[i−1]=a[i]

2. $a[i-1]+2=a[i]$a[i−1]+2=a[i]

3. $a[i-1]-2=a[i]$a[i−1]−2=a[i]

来逐一解释一下：

1. $a[i-1]=a[i]$a[i−1]=a[i]

   这说明青蛙越过这两个区间的合法情况是这样的：

   （其中的红线代表青蛙跳跃的路线）

   

   即如果有青蛙经过区间$(i-1,i)$(i−1,i)，它必定要经过$(i,i+1)$(i,i+1)，否则$a[i-1]\neq a[i]$a[i−1]̸​=a[i]。而由于题目要求输出任意一种方案，我们不妨令青蛙$i$i跳到了原地。

2. $a[i-1]+2=a[i]$a[i−1]+2=a[i]

   还是画个图先：

   

   意思就是，该经过的还是两个都得经过，不过$i$i要往右跳，另一个人要从右边跳到$i$i，这样才能使得$a[i]=a[i-1]+2$a[i]=a[i−1]+2。而由于题目要求输出任意一种方案，我们不妨设$i$i与右边的某只青蛙互换了位置。然后我们将$i$i插入一个栈里面。

3. $a[i-1]-2=a[i]$a[i−1]−2=a[i]

   图：

   

   意思就是，该经过的还是两个都得经过，不过$i$i要往左跳，另一个人要从左边跳到$i$i，这样才能使得$a[i]=a[i-1]-2$a[i]=a[i−1]−2。而由于题目要求输出任意一种方案，我们不妨设$i$i与左边的某只青蛙互换了位置。所以我们取栈顶的元素，这个元素$x$x代表着$x$x要与$x$x右边的某个元素交换位置，而由于我们是从小到大循环遍历$i$i的，所以第$i$i只青蛙刚好符合条件。所以$x$x与$i$i互换位置（$p[i]=x,p[x]=i$p[i]=x,p[x]=i）。

最后把$p[i]$p[i]输出了就好了。

代码如下：

#include<bits/stdc++.h>

#define N 200010

using namespace std;

int n,a[N],p[N],st[N],top;

void NO()
{
	puts("No");
	exit(0);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==a[i-1])//自己跳自己
			p[i]=i;
		else if(a[i]==a[i-1]+2)//i往右跳 
			st[++top]=i;
		else if(a[i]==a[i-1]-2)//i往左跳
		{
			if(!top)//i往左跳，如果左边没人跳过来，就说明i跳不过去 
				NO();
			p[st[top]]=i;
			p[i]=st[top--];
		}
		else
			NO();//因为每一个a[i]得是偶数且与相邻两个的相差不超过2，其他情况不符合 
	}
	if(top)//栈里还有青蛙要往右跳，说明不合法 
		NO();
	puts("Yes");
	for(int i=1;i<=n;i++)
		printf("%d ",p[i]);
	return 0;
}