样例下载

题目描述

小辉同学在第 1 行写下 1 ~ n 的一个排列。然后从第 2 行开始进行如下操作：

从左至右依次将上一行相邻两个数的和写在当前行。显然，第 2 行有 n-1 个数。

重复以上操作，直至最后一行即第 n 行只有一个数。

不幸的是，小辉同学刚刚完成，墨水污染了其他所有行，只能看清第二行的数。

现在请你根据第二行的数倒推出第一行的排列。答案可能不止一种，你需要输出第一行字典序最小的那个排列。

输入格式

第一行：一个整数 n

第二行：n-1 个整数，表示小辉在第二行写的数

输出格式

一行，n 个整数，表示满足题目要求的排列。数据保证有解。

样例输入

3
3 4

样例输出

2 1 3

数据范围

40%：$1 ≤ n ≤ 10$;

100%：$1 ≤ n ≤ 10^3$。