Foto di gruppo

Il fattore John ha allineato le sue $n$ vacche, numerate da $1$ a $n$, per una foto. Inizialmente aveva pianificato che la $i$-esima vacca da sinistra avesse il numero a_i, e aveva scritto la permutazione a_1, a_2, \ldots, a_n su un foglio di carta. Sfortunatamente, questo foglio è stato rubato dal fattore Nhож.

Tuttavia, John ha la possibilità di ricostruire la permutazione che aveva originariamente scritto. Prima che il foglio con la permutazione fosse rubato, Bessie aveva scritto una sequenza b_1, b_2, \ldots, b_{n-1} tale che b_i = a_i + a_{i+1} per tutti gli $i$ (1 \le i < n).

In base alle informazioni fornite da Bessie, aiuta John a ricostruire la permutazione $a$ lessicograficamente minima che potrebbe aver generato la sequenza $b$. Una permutazione $x$ è lessicograficamente minore di una permutazione $y$ se, per qualche $j$, x_i = y_i per tutti gli i < j e x_j < y_j (in altre parole, le due permutazioni sono identiche fino a un certo punto, in cui $x$ è minore di $y$).

È garantito che esista almeno una tale permutazione $a$.