![](http://img.atcoder.jp/assets/top/img/flag-lang/ja.png)
![](http://img.atcoder.jp/assets/top/img/flag-lang/en.png)
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
1 と -1 のみからなる長さ N の数列 A = (A_1, \ldots, A_N) が与えられます.
以下の条件をすべて満たす整数列 x = (x_1, \ldots, x_N) が存在するか否かを判定し, 存在する場合にはそのような整数列をひとつ答えてください.
- 任意の i (1\leq i\leq N) に対して |x_i| \leq 10^{12}.
- x は狭義単調増加である.つまり x_1 < \cdots < x_N.
- \sum_{i=1}^N A_ix_i = 0.
制約
- 1\leq N\leq 2\times 10^5
- A_i \in \lbrace 1, -1\rbrace
入力
入力は以下の形式で標準入力から与えられます.
N A_1 \ldots A_N
出力
問題の条件をすべて満たす整数列 x が存在するならば Yes
を,そうでなければ No
を出力してください.Yes
の場合には,2 行目にそのような整数列 x の各要素を,空白で区切って 1 行で出力してください.
x_1 \ldots x_N
条件を満たす整数列が複数存在する場合は,どれを出力しても正解となります.
入力例 1
5 -1 1 -1 -1 1
出力例 1
Yes -3 -1 4 5 7
この出力について \sum_{i=1}^NA_ix_i= -(-3) + (-1) - 4 - 5 + 7 = 0 となります.
入力例 2
1 -1
出力例 2
Yes 0
入力例 3
2 1 -1
出力例 3
No
Score : 600 points
Problem Statement
You are given a sequence of length N, A = (A_1, \ldots, A_N), consisting of 1 and -1.
Determine whether there is an integer sequence x = (x_1, \ldots, x_N) that satisfies all of the following conditions, and print one such sequence if it exists.
- |x_i| \leq 10^{12} for every i (1\leq i\leq N).
- x is strictly increasing. That is, x_1 < \cdots < x_N.
- \sum_{i=1}^N A_ix_i = 0.
Constraints
- 1\leq N\leq 2\times 10^5
- A_i \in \lbrace 1, -1\rbrace
Input
The input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
If there is an integer sequence x that satisfies all of the conditions in question, print Yes
; otherwise, print No
. In case of Yes
, print the elements of such an integer sequence x in the subsequent line, separated by spaces.
x_1 \ldots x_N
If multiple integer sequences satisfy the conditions, you may print any of them.
Sample Input 1
5 -1 1 -1 -1 1
Sample Output 1
Yes -3 -1 4 5 7
For this output, we have \sum_{i=1}^NA_ix_i= -(-3) + (-1) - 4 - 5 + 7 = 0.
Sample Input 2
1 -1
Sample Output 2
Yes 0
Sample Input 3
2 1 -1
Sample Output 3
No