题目描述

小杰有一个长为n的排列p，但大白熊将其隐藏了起来。现在大白熊给了小杰一个长度为n-1的数组a，其中$a_i$ = $p_i$ + $p_{i+1}$ 小杰想用数组a还原出排列p来，你能帮帮她吗?

排列是指：1-n之间每个数字只出现一次。

输入描述

输入包含两行。

第一行一个正整数n，表示排列p的长度。

第二行n-1个正整数$a_i$，表示题中所述数组a的元素。 $1 \le n \le 2 * 10^3$;

$1 < a_i < n + (n - 1)$。

输出描述

输出包含一行n个数字，表示还原出来的排列p。如果有多解，请输出字典序最小的解，但如果无解，请输出-1。

输入示例

4
5 7 5

输出示例

1 4 3 2

提示信息

时间限制：c/c++：1s；其他语言：3s。