34127번 - 래환이의 블록 쌓기 이야기 스페셜 저지

문제

래환이는 도시계획과환경 시간에 블록을 이용해 도시를 만드는 과제를 받았다. 래환이는 $N$개의 빌딩이 가로 방향 일직선으로 늘어선 도시를 만들었다. 그중 왼쪽에서부터 $i$번째 빌딩의 높이는 $H_i$이다.

완성된 도시를 바라보고 있던 래환이의 팀원 넙죽이는 들쭉날쭉한 빌딩의 높이가 마음에 들지 않았다. 그래서 넙죽이는 각 빌딩의 높이가 오름차순을 이루도록, $i$번째 빌딩의 높이를 $C_i$만큼 몰래 바꾸려고 한다. 즉, $N$개의 정수 $C_1, C_2, \cdots, C_N$을 선택하여 $i$번째 빌딩의 높이를 $H_i + C_i$로 바꾸되, $H_1 + C_1 < H_2 + C_2 < \cdots < H_N + C_N$이 성립하도록 하려고 한다.

래환이는 여분의 블록을 남기지 않았고, 너무 많은 블록을 제거하면 래환이가 알아차릴 수 있기 때문에 바꾼 뒤 각 빌딩의 높이의 총합은 바꾸기 전 각 빌딩의 높이의 총합과 같거나 1ドル$ 작아야 한다. 또, 바꾼 뒤의 도시에서도 모든 빌딩의 높이가 1ドル$ 이상이어야 한다.

또한 넙죽이는 홀수와 짝수를 구분하는 일에 민감하기 때문에, 홀수 번째 빌딩 각각의 높이가 그대로 유지되거나 홀수만큼 바뀌게끔 해야 하고, 짝수 번째 빌딩에서는 빌딩 각각의 높이가 그대로 유지되거나 짝수만큼 바뀌게끔 해야 한다.

넙죽이가 도시를 완성할 수 있도록 각 빌딩의 높이를 어떻게 바꿔야 할지 알려주자!

입력

첫 번째 줄에 정수 $N$이 주어진다. $(2 \le N \le 2\times 10^5)$

두 번째 줄에 $N$개의 정수 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 주어진다. $(1 \le H_i \le 2 \times 10^5)$

출력

넙죽이의 조건에 맞는 도시를 만들 수 있는 경우 첫 번째 줄에 YES를 출력한다.

두 번째 줄에는 $N$개의 정수 $C_1, C_2, \cdots, C_N$을 공백으로 구분하여 출력한다.

넙죽이의 조건에 맞는 도시를 만들 수 없는 경우 첫 번째 줄에 NO를 출력한다.

제한

힌트