32517번 - 평점 변환 2 스페셜 저지

문제

2023학년도까지 대구과학고에서는 학생들의 한 학기 동안의 성적에 따라 1ドル$ 이상 10ドル^9$ 이하의 정수 가운데 하나로 평어를 부여하였다. 수가 낮을수록 좋은 평어이므로, 1ドル$이 가장 좋은 평어이고 10ドル^9$가 가장 나쁜 평어이다. 하지만 이러한 평어 체제에서는 이전 학기 대비 성장 정도가 평어에 반영되지 않으므로, 학생들이 자신의 성장 과정보다는 상대적 위치에 집착하게 되는 부작용이 있었다. 그래서 2024학년도부터는 성적에 따라 매겨진 평어를 기준으로 보았을 때, 이전 학기들의 평균과 비교하여 성적이 좋아진 경우에는 평어를 1ドル$ 감소하는 식으로 평어를 부여하기로 했다. 구체적으로, 2023학년도 이전을 기준으로 한 $N$학기 동안의 평어가 첫 학기부터 $N$번째 학기까지 순서대로 $a_1, a_2, …, a_N$ 이라고 하면, 평어 $b_1, b_2, …, b_N$은 다음과 같이 계산된다.

• $b_1 = a_1$
• 각 1ドル \leq i \leq N-1$ 에 대해서, $a_{i+1}<\frac{1}{i}\sum_{j=1}^{i}a_j$ 이면 $b_{i+1} = a_{i+1} - 1$ 이고, 그렇지 않으면 $b_{i+1}= a_{i+1}$ 이다.

위의 정의에 따르면 2024학년도 이후의 평어는 항상 0ドル$ 이상 10ドル^9$ 이하의 정수가 된다.

2024년에 대구과학고에 입학하여 $N$학기 동안 재학한 은성이는, 자신의 평어를 새로운 평어에 따라 받아 왔다. 은성이는 문득 자신의 평어가 2023학년도 이전의 평어로는 어디에 해당할지 궁금해졌다. 은성이의 $N$학기 동안의 평어 $b_1, b_2, …, b_N$ 이 주어졌을 때, 이 평어로 변환될 수 있는 2023학년도 이전 기준의 평어 $a_1, a_2, …, a_N$ 으로 가능한 것을 아무 것이나 하나 구하여라. 단, 전산 오류로 인하여 평어가 잘못 계산되어, 가능한 $a_1, a_2, …, a_N$이 존재하지 않는 경우에는 존재하지 않음을 판별해야 한다.

입력

첫째 줄에 은성이가 대구과학고에 다닌 학기의 수 $N$이 주어진다.

둘째 줄에 은성이의 평어 $b_1, b_2, …, b_N$ 이 주어진다.

출력

첫째 줄에 2023학년도 이전 기준의 평어의 수열 $a_1, a_2, \ldots, a_N$ 을 공백을 사이에 두고 출력한다. 조건을 만족하는 수열이 여러 개인 경우 아무 것이나 하나를 출력하며, 수열이 없는 경우 대신 $-1$을 출력한다.

제한

• 1ドル \le N \le 500\ 000$
• 각 1ドル\le i\le N$에 대하여, 0ドル \le b_i \le 10^9$
• 주어지는 모든 수는 정수이다.

힌트