Grade Conversion 2

Until the 2023 academic year, Daegu Science High School gave each student a semester grade, an integer from $1$ to $10^9$, based on that semester's performance. A lower number meant a better grade, so $1$ was the best and $10^9$ was the worst. This system did not reflect how much a student improved from the previous semester, so students focused on their rank relative to others instead of their own growth.

Starting in the 2024 academic year, the school changed the rule. If a student's grade was lower than the average of their earlier grades, the grade was reduced by $1$. Specifically, let $a\_1, a\_2, …, a\_N$ be the grades for semesters $1$ through $N$ under the old system, which was in use through the 2023 academic year. Then the grades $b\_1, b\_2, …, b\_N$ are computed as follows.

• $b\_1 = a\_1$
• For each $1 \leq i \leq N-1$, if $a\_{i+1}<\frac{1}{i}\sum\_{j=1}^{i}a\_j$, then $b\_{i+1} = a\_{i+1} - 1$. Otherwise, $b\_{i+1}= a\_{i+1}$.

Under this definition, grades from the 2024 academic year onward are always integers from $0$ to $10^9$.

The first line contains $N$, the number of semesters Eunseong attended.

The second line contains Eunseong's grades $b\_1, b\_2, …, b\_N$.

Print the old-system grades $a\_1, a\_2, \ldots, a\_N$ separated by spaces. If several sequences satisfy the conditions, print any one of them. If no such sequence exists, print $-1$ instead.

• $1 \le N \le 500\ 000$
• For each $1\le i\le N$, $0 \le b\_i \le 10^9$
• All given numbers are integers.