Фотострільба

Фермер Джон вишикував $n$ своїх корів, пронумерованих $1$ до $n$, для фотознімка. Спочатку він планував, що $i$-та корова зліва буде корова з номером a_i, і виписав перестановку a_1, a_2, \ldots, a_n на аркуші паперу. На жаль, цей листок вкрав фермер Нхож.

Проте Джон може відновити перестановку, яку він спочатку виписав. Перед тим, як листок із перестановкою було вкрадено, Бессі виписала послідовність b_1, b_2, \ldots, b_{n-1} таку, що b_i = a_i + a_{i+1} для всіх $i$ (1 \le i < n).

За інформацією від Бессі, допоможіть Джону відновити лексикографічно мінімальну перестановку $a$, яка могла породити $b$. Перестановка $x$ є лексикографічно меншою за перестановку $y$, якщо для деякого $j$, x_i = y_i для всіх i < j та x_j < y_j (іншими словами, дві перестановки ідентичні до певної точки, у якій $x$ менше ніж $y$).

Гарантовано, що існує принаймні одна така перестановка $a$.