给定一个1～n的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。 例如: 3 1 2 4 4 3 6 7 9 16 现在如果知道n和最后得到的数字sum，请求出最初序列a[i]，为1～n的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。

题目描述：给定一个1~n的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复上述操作，直到得到的序列都比上一次的序列更短，最终只剩一个数字。现在如果知道n和最后得到的数字sum，求最初的排列a[i]，为1~n的一个排列。

题解：本题实际上是一个迭代的过程，从最终的数字sum开始反推回去，直到得到最初的排列a[i]。每一次反推的结果都是一个新的数字序列，用长度作为排序的关键字，得到的就是当前数字序列的排列方式。将这个排列与上一次得到的排列进行比较，找到不同的位置，即为两个相加得到这个新序列的原始数字，重复这个过程，直到得到最初的数字序列。

比如样例中的情况，最后得到的数字为16，反推回去得到第一个新序列为7 9，长度为2，是最短的。那么找到与原序列的差别，可以发现是1和2的位置变换了，也就是a[1]+a[2]得到了7，而a[2]+a[3]得到了9，那么得到的新序列为4 3 6，重复上述过程反推，最终得到初始的序列为3 1 2 4。

相关问题

给定一个1～n的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字

这道题要求给定一个长度为1~n的数组a[i]，每次将相邻两个数相加，得到一个新的序列，再对新序列重复这样的操作，直到最终只剩一个数字。对于每次得到的序列，需要比较它们的长度，取最短的序列长度加1，最终只保留一个数字。

问题描述\n 给定一个1～n的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。\n 例如:\n 3 1 2 4

这道题目要求我们对一个给定的排列进行相邻两个数相加的操作，直到最终只剩下一个数字。每次操作后，序列长度会减少1。

举个例子，如果给定的排列是3 1 2 4，那么第一次操作后得到的新序列是4 3 6，第二次操作后得到的新序列是7 9，最终只剩下数字16。

我们需要写一个程序来实现这个操作，并输出最终的结果。